Method and system for efficiently matching events with subscribers in a content-based publish-subscribe system

• US 6,839,730 B1
• Filed: 07/14/2000
• Issued: 01/04/2005
• Est. Priority Date: 07/14/2000
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Ramabhadran, Narayanan S.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): Qureshi, Shabana
• Application Number:
  US09/616,498
• Time in Patent Office: 1,635 Days
• Field of Search: 709/201, 707/3, 707/10, 707/1, 707/103, 707200-206
• US Class Current: 709/201
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method is provided for efficiently solving the matching problem in content-based publish-subscribe systems. Subscribers may define arbitrary boolean predicates as conditions to subscribe to the published event. The subscribers and their predicates can be organized in the form of a virtual Direct Acyclic Graph (DAG) such that a traversal of the DAG yields one or more matching subscribers. The present invention improves upon the conventional method of linearly matching individual subscribers against an event.

Claims

1. A method for matching a published event with one or more subscribers in a content-based publish-subscribe system in a computer network, each subscriber having one or more predetermined predicates, the method comprising:

creating a virtual Direct Acyclic Graph (DAG) including one or more arbitrary boolean tests representing the predetermined predicates;

eliminating, upon publishing the event, one or more subscribers, at least one of whose predicates is not satisfied while the DAG is traversed; and

identifying at least one matching subscriber if all the predicates of the matching subscriber are satisfied,

wherein the DAG has a root node, one or more leaf nodes representing subscribers, and one or more non-leaf nodes representing the boolean tests which are formed by boolean connectors and

wherein the step of creating further includes constructing the DAG in a top-down fashion so that common predicates shared by the subscribers are examined first and a minimal number of boolean tests are conducted to identify the matching subscribers.

2. The method of claim 1 further includes, when a new subscriber is added, adding the new predicates of the new subscriber to the DAG recursively starting from the root node, and adding a leaf node at any node in the DAG where the boolean test at the node is satisfied.

3. The method of claim 1 wherein each non-leaf node directs toward other leaf nodes or non-leaf nodes based on the results of the boolean test at the non-leaf node.

4. The method of claim 3 wherein the boolean test result is one of True, False, or Null.

5. The method of claim 1 wherein the boolean connectors are AND, OR, NOT and parenthesis.

6. The method of claim 1 wherein the predetermined predicate includes an atomic test, a disjunction of sub predicates, a conjunction of sub predicates, or a negation of a sub predicates.

7. A computer program for matching a published event with one or more subscribers in a content-based publish-subscribe system in a computer network, each subscriber having one or more predetermined predicates, the program comprising programs for:

creating in a top-down fashion a virtual Direct Acyclic Graph (DAG) including one or more arbitrary boolean tests representing the predetermined predicates so that common predicates shared by the subscribers are examined first and a minimum number of boolean tests are thus conducted to identify the matching subscriber;

eliminating, upon publishing the event, one or more subscribers wherein at least one of whose predicates is not satisfied while the DAG is travesed; and

identifying at least one matching subscriber if all the predicates of the matching subscriber are satisfied,

wherein the DAG has a root node, one or more leaf nodes representing subscribers, and one or more non-leaf nodes representing the boolean tests formed by boolean connectors.

8. The program of claim 7 wherein the program for creating further includes, when a new subscriber is added, adding the new predicates of the new subscriber to the DAG recursively starting from the root node, and adding a leaf node at any node in the DAG where the boolean test at the node is satisfied.

9. The program of claim 7 wherein each non-leaf node directs toward other leaf nodes or non-leaf nodes based on the test result at the non-leaf node.

10. The program of claim 9 wherein the test result is one of True, False, or Null.

11. The program of claim 7 wherein the boolean connectors are AND, OR, NOT and parenthesis.

12. The program of claim 7 wherein the predicate includes an atomic test, a disjunction of sub predicates, a conjunction of sub predicates, or a negation of a sub predicates.