Name
Abstract | ||
|---|---|---|
Content-based publish/subscribe systems allow matching the content of events with predicates in the subscriptions. However, most existing systems only allow a limited set of operators, such as comparison on primitive data types (string, integer, etc). In this paper, we consider a publish/subscribe system that supports more flexible events/subscriptions with the use of advanced, yet potentially expensive, matching operators. Examples of such operators are pattern recognizers on multimedia data and spatial operators on location data. We study a critical problem in these publish/subscribe systems, namely how to optimize the matching process for a large number of subscriptions. This is achieved by exploiting the overlap in the subscriptions and sharing the operator evaluation results whenever possible. We formulate the optimal subscription evaluation problem and show that it is NP-Hard. We propose an efficient d-approximation algorithm, where d is the maximum number of operators in one subscription, as well as a heuristic algorithm that can further improve the system performance in practice. Our experiment results show that the proposed algorithms can reduce the matching cost by up to 80%, as compared to a naive strategy that evaluates the subscriptions independently. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1266894.1266940 | DEBS |
Keywords | Field | DocType |
overlapping subscription,critical problem,multimedia data,scalable event,location data,matching cost,existing system,sub system,efficient d-approximation algorithm,large number,matching process,heuristic algorithm,primitive data type,publish subscribe,limit set,data type,system performance,optimization | Integer,Publication,Heuristic (computer science),Computer science,Theoretical computer science,Location data,Operator (computer programming),Distributed computing,Primitive data type,Scalability | Conference |
Citations | PageRank | References |
8 | 0.94 | 20 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhen Liu | 1 | 1088 | 102.40 |
| Srinivasan Parthasarathy | 2 | 4666 | 375.76 |
| Anand Ranganathan | 3 | 2696 | 164.67 |
| Hao Yang | 4 | 660 | 48.26 |