US6839730B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for efficiently matching events with subscribers in a content-based publish-subscribe system
Assignee: RPX Corp
•
Filing: 2000-07-14
•
Granted: 2005-01-04
•
Expires: 2020-07-14
Abstract
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.
Inventors
- 👤 Narayanan S. Ramabhadran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 16:37
CPC Classifications
H; H04; H04L; H04L67/00; H04L67/2866; H04L67/30; H04L67/306; H04L9/00; H04L9/40; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/329; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
160 words
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.
Claim 2
Independent Claim
160 words
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.
Claim 3
Dependent Claim
50 words
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.
Claim 4
Dependent Claim
29 words
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.
Claim 5
Dependent Claim
17 words
The method of claim 3 wherein the boolean test result is one of True, False, or Null.
Claim 6
Dependent Claim
15 words
The method of claim 1 wherein the boolean connectors are AND, OR, NOT and parenthesis.
Claim 7
Dependent Claim
30 words
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.
Claim 8
Dependent Claim
152 words
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.
Claim 9
Dependent Claim
152 words
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.
Claim 10
Dependent Claim
55 words
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.
Claim 11
Dependent Claim
26 words
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.
Claim 12
Dependent Claim
16 words
The program of claim 9 wherein the test result is one of True, False, or Null.
Claim 13
Dependent Claim
15 words
The program of claim 7 wherein the boolean connectors are AND, OR, NOT and parenthesis.
Claim 14
Dependent Claim
29 words
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.
References Cited (Backward Citations)
US5659725A
Cited
US6065009A
Cited
US6091724A
Cited
US6216132B1
Cited
US6108645A
Cited
US6169989B1
Cited
US6725227B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2008-01-04 | 2008-07-05 | 2009-01-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2012-01-04 | 2012-07-05 | 2013-01-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2016-01-04 | 2016-07-05 | 2017-01-04 | $7700.00 | Window Closed / Lapsed |