Method and system for matching consumers to events

• US 6,216,132 B1
• Filed: 11/20/1997
• Issued: 04/10/2001
• Est. Priority Date: 11/20/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sturman, Daniel Charles, Astley, Mark Christopher, Strom, Robert Evan, Chandra, Tushar Deepak
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): LE, UYEN T
• Application Number:
  US08/975,280
• Time in Patent Office: 1,237 Days
• Field of Search: 707/103, 707/10, 395/733, 395/670, 395/682, 395/872, 395/8, 395/9, 395/101, 395/104, 706/48, 709/229
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A generalized search data structure is used to match consumers to events in event computing systems. The search data structure includes one or more paths from a root of the structure to one or more leaves of the structure. Each path has at least one level and each level corresponds to a filter attribute. The value of at least one filter attribute in at least one path is a don'"'"'t care value indicating traversal of that path is guaranteed to proceed. In addition to following the path with the don'"'"'t care value, one or more additional paths may also be followed. Thus, traversal of the search data structure may yield zero or more results, indicating that zero or more consumers match the specified event. Various optimizations of the search data structure are possible.

Claims

1. A method of determining zero or more consumers interested in an event, said method comprising:

receiving an event; and

using a search data structure to determine zero or more consumers interested in said event, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure.

2. The method of claim 1, wherein at least one of the attributes having said don'"'"'t care value further has a second value, and wherein traversal of a second path also proceeds upon successful testing of the second value, wherein said second path comprises said another path.

3. The method of claim 1, wherein said using comprises traversing said search data structure from a root of said search data structure to zero or more leaves of said search data structure, said zero or more leaves indicating said zero or more consumers interested in said event.

4. The method of claim 3, wherein said event comprises one or more event attribute values and wherein said traversing comprises using said one or more event attribute values to reach said zero or more leaves.

5. The method of claim 1, further comprising building said search data structure.

6. The method of claim 5, wherein said building comprises:

specifying, by a consumer, a filter having one or more attribute values, said one or more attribute values corresponding to said one or more attributes; and

inserting said one or more attribute values into said search data structure.

7. The method of claim 6, wherein said inserting comprises storing said one or more attribute values in at least one node of said search data structure.

8. The method of claim 6, wherein said building further comprises indicating within said search data structure said consumer specifying said filter.

9. The method of claim 6, further comprising inserting into said search data structure one or more other attribute values specified by one or more other filters provided by one or more consumers, wherein a plurality of paths is created and wherein paths having a common prefix are merged.

10. The method of claim 9, wherein said event comprises one or more event attribute values, and wherein said using comprises traversing one or more paths of said search data structure using said event attribute values.

11. The method of claim 5, wherein said building comprises transforming said search data structure.

12. The method of claim 11, wherein a plurality of consecutive attributes in said path have a don'"'"'t care value, and wherein said transforming comprises combining levels within said path corresponding to said plurality of consecutive attributes having said don'"'"'t care values.

13. The method of claim 12, wherein said plurality of consecutive attributes in said path only have said don'"'"'t care value.

14. The method of claim 1, wherein said search data structure comprises a plurality of paths, and wherein said method further comprises computing a successor set for a node of said search data structure, said successor set defining how to traverse said search data structure after reaching said node.

15. The method of claim 14, wherein said computing comprises:

determining one or more subpaths associated with said node; and

identifying one or more successor nodes reached by traversing said one or more subpaths, said one or more successor nodes comprising said successor set.

16. The method of claim 15, wherein a path to said node is represented by one or more attribute values, at least one of said one or more attribute values having a concrete value, and wherein said determining comprises:

replacing one concrete attribute value with a don'"'"'t care value, wherein a subpath is created; and

repeating said replacing for any other attribute values having a concrete value, wherein only one attribute value is replaced at any given time.

17. The method of claim 16, wherein if a subpath is created that has a non-existent node, one or more successor nodes of said non-existent node is identified in said successor set, instead of said non-existent node.

18. The method of claim 1, wherein said search data structure comprises a plurality of sub-search data structures.

19. The method of claim 18, wherein said using comprises:

selecting one of said sub-search data structures; and

traversing said selected sub-search data structure to determine said zero or more consumers.

20. The method of claim 19, wherein said event comprises a plurality of event attributes, and wherein said selecting comprises using one or more values of one or more chosen attributes of said plurality of event attributes to select said subsearch data structure to be traversed.

21. The method of claim 5, wherein said building further comprises ordering said one or more attributes based upon its relative likelihood of having a concrete value in one or more filters, wherein those attributes most likely to have concrete values are tested earlier than those less likely to have concrete values.

22. The method of claim 1, wherein said zero or more consumers are subscribers of a publish/subscribe system and said receiving comprises receiving, from a publisher of said publish/subscribe system, said event.

23. A method of publishing an event in a publish/subscribe system, said method comprising:

providing, by a publisher of said publish/subscribe system, an event to be published to one or more subscribers of said publish/subscribe system, said event being independent of a group association and lacking a group identifier;

determining said one or more subscribers interested in said event, said determining comprising using a search data structure to determine said one or more subscribers, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure; and

publishing said event to one or more subscribers indicating interest in said event.

24. The method of claim 23, further comprising providing, by said one or more subscribers, one or more filters indicating interest in said event.

25. The method of claim 24, wherein at least one filter of said one or more filters includes a plurality of attributes to be used in indicating interest in said event.

26. The method of claim 24, wherein said one or more filters is located in said publish/subscribe system independent of said one or more subscribers.

27. The method of claim 23, wherein said using comprises traversing said search data structure from a root of said search data structure to one or more leaves of said search data structure, said one or more leaves indicating said one or more subscribers interested in said event.

28. The method of claim 27, wherein said event comprises one or more event attribute values and wherein said traversing comprises using said one or more event attribute values to reach said one or more leaves.

29. The method of claim 23, further comprising building said search data structure.

30. The method of claim 23, further comprising optimizing said search data structure.

31. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of determining zero or more consumers interested in an event, said method comprising:

receiving an event; and

using a search data structure to determine zero or more consumers interested in said event, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure.

32. The at least one program storage device of claim 31, wherein at least one of the attributes having said don'"'"'t care value further has a second value, and wherein traversal of a second path also proceeds upon successful testing of the second value, wherein said second path comprises said another path.

33. The at least one program storage device of claim 31, wherein said using comprises traversing said search data structure from a root of said search data structure to zero or more leaves of said search data structure, said zero or more leaves indicating said zero or more consumers interested in said event.

34. The at least one program storage device of claim 33, wherein said event comprises one or more event attribute values and wherein said traversing comprises using said one or more event attribute values to reach said zero or more leaves.

35. The at least one program storage device of claim 31, wherein said method further comprises building said search data structure.

36. The at least one program storage device of claim 35, wherein said building comprises:

specifying, by a consumer, a filter having one or more attribute values, said one or more attribute values corresponding to said one or more attributes; and

inserting said one or more attribute values into said search data structure.

37. The at least one program storage device of claim 36, wherein said inserting comprises storing said one or more attribute values in at least one node of said search data structure.

38. The at least one program storage device of claim 36, wherein said building further comprises indicating within said search data structure said consumer specifying said filter.

39. The at least one program storage device of claim 36, wherein said method further comprises inserting into said search data structure one or more other attribute values specified by one or more other filters provided by one or more consumers, wherein a plurality of paths is created and wherein paths having a common prefix are merged.

40. The at least one program storage device of claim 39, wherein said event comprises one or more event attribute values, and wherein said using comprises traversing one or more paths of said search data structure using said event attribute values.

41. The at least one program storage device of claim 39, wherein said building comprises transforming said search data structure.

42. The at least one program storage device of claim 41, wherein a plurality of consecutive attributes in said path have a don'"'"'t care value, and wherein said transforming comprises combining levels within said path corresponding to said plurality of consecutive attributes having said don'"'"'t care values.

43. The at least one program storage device of claim 42, wherein said plurality of consecutive attributes in said path only have said don'"'"'t care value.

44. The at least one program storage device of claim 31, wherein said search data structure comprises a plurality of paths, and wherein said method further comprises computing a successor set for a node of said search data structure, said successor set defining how to traverse said search data structure after reaching said node.

45. The at least one program storage device of claim 44, wherein said computing comprises:

determining one or more subpaths associated with said node; and

identifying one or more successor nodes reached by traversing said one or more subpaths, said one or more successor nodes comprising said successor set.

46. The at least one program storage device of claim 45, wherein a path to said node is represented by one or more attribute values, at least one of said one or more attribute values having a concrete value, and wherein said determining comprises:

replacing one concrete attribute value with a don'"'"'t care value, wherein a subpath is created; and

repeating said replacing for any other attribute values having a concrete value, wherein only one attribute value is replaced at any given time.

47. The at least one program storage device of claim 46, wherein if a subpath is created that has a non-existent node, one or more successor nodes of said non-existent node is identified in said successor set, instead of said non-existent node.

48. The at least one program storage device of claim 31, wherein said search data structure comprises a plurality of sub-search data structures.

49. The at least one program storage device of claim 48, wherein said using comprises:

selecting one of said sub-search data structures; and

traversing said selected sub-search data structure to determine said zero or more consumers.

50. The at least one program storage device of claim 49, wherein said event comprises a plurality of event attributes, and wherein said selecting comprises using one or more values of one or more chosen attributes of said plurality of event attributes to select said sub-search data structure to be traversed.

51. The at least one program storage device of claim 35, wherein said building further comprises ordering said one or more attributes based upon its relative likelihood of having a concrete value in one or more filters, wherein those attributes most likely to have concrete values are tested earlier than those less likely to have concrete values.

52. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of publishing an event in a publish/subscribe system, said method comprising:

providing, by a publisher of said publish/subscribe system, an event to be published to one or more subscribers of said publish/subscribe system, said event being independent of a group association and lacking a group identifier;

determining said one or more subscribers interested in said event, said determining comprising using a search data structure to determine said one or more subscribers, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure; and

publishing said event to one or more subscribers indicating interest in said event.

53. The at least one program storage device of claim 52, wherein said method further comprises providing, by said one or more subscribers, one or more filters indicating interest in said event.

54. The at least one program storage device of claim 53, wherein at least one filter of said one or more filters includes a plurality of attributes to be used in indicating interest in said event.

55. The at least one program storage device of claim 53, wherein said one or more filters is located in said publish/subscribe system independent of said one or more subscribers.

56. The at least one program storage device of claim 52, wherein said using comprises traversing said search data structure from a root of said search data structure to one or more leaves of said search data structure, said one or more leaves indicating said one or more subscribers interested in said event.

57. The at least one program storage device of claim 56, wherein said event comprises one or more event attribute values and wherein said traversing comprises using said one or more event attribute values to reach said one or more leaves.

58. The at least one program storage device of claim 52, wherein said method further comprises building said search data structure.

59. The at least one program storage device of claim 52, wherein said method further comprises optimizing said search data structure.

60. An article of manufacture, comprising:

at least one computer usable medium having computer readable program code means embodied therein for causing the determining of zero or more consumers interested in an event, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to receive an event; and

computer readable program code means for causing a computer to use a search data structure to determine zero or more consumers interested in said event, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure.

61. The article of manufacture of claim 60, wherein at least one of the attributes having said don'"'"'t care value further has a second value, and wherein traversal of a second path also proceeds upon successful testing of the second value, wherein said second path comprises said another path.

62. The article of manufacture of claim 60, wherein said computer readable program code means for causing a computer to use comprises computer readable program code means for causing a computer to traverse said search data structure from a root of said search data structure to zero or more leaves of said search data structure, said zero or more leaves indicating said zero or more consumers interested in said event.

63. The article of manufacture of claim 60, further comprising computer readable program code means for causing a computer to build said search data structure.

64. The article of manufacture of claim 63, wherein said computer readable program code means for causing a computer to build comprises computer readable program code means for causing a computer to transform said search data structure.

65. The article of manufacture of claim 62, wherein a plurality of consecutive attributes in said path have a don'"'"'t care value, and wherein said computer readable program code means for causing a computer to transform comprises computer readable program code means for causing a computer to combine levels within said path corresponding to said plurality of consecutive attributes having said don'"'"'t care values.

66. The article of manufacture of claim 60, wherein said search data structure comprises a plurality of paths and wherein said article of manufacture further comprises computer readable program code means for causing a computer to compute a successor set for a node of said search data structure, said successor set defining how to traverse said search data structure after reaching said node.

67. The article of manufacture of claim 60, wherein said search data structure comprises a plurality of sub-search data structures.

68. An article of manufacture, comprising:

at least one computer usable medium having computer readable program code means embodied therein for causing the publishing of an event in a publish/subscribe system, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to provide an event to be published to one or more subscribers of said publish/subscribe system, said event being independent of a group association and lacking a group identifier;

computer readable program code means for causing a computer to determine said one or more subscribers interested in said event, said determining comprising using a search data structure to determine said one or more subscribers, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure; and

computer readable program code means for causing a computer to publish said event to one or more subscribers indicating interest in said event.

69. The article of manufacture of claim 68, further comprising computer readable program code means for causing a computer to build said search data structure.

70. The article of manufacture of claim 68, further comprising computer readable program code means for causing a computer to optimize said search data structure.

71. A system of determining zero or more consumers interested in an event, said system comprising:

means for receiving an event; and

a search data structure usable in determining zero or more consumers interested in said event, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure.

72. A system of publishing an event in a publish/subscribe system, said system comprising:

a publisher of said publish/subscribe system adapted to provide an event to be published to one or more subscribers of said publish/subscribe system, said event being independent of a group association and lacking a group identifier;

means for determining said one or more subscribers interested in said event, said means for determining comprising a search data structure useable in determining said one or more subscribers, said search data structure comprising a path having one or more levels, said one or more levels corresponding to one or more attributes, and wherein a value of at least one attribute is a don'"'"'t care value meaning traversal of the path is guaranteed to proceed irrespective of whether another path is also followed, wherein when said another path is also followed said search data structure comprises a spatially parallel search structure; and

means for publishing said event to one or more subscribers indicating interest in said event.