Abstract
Content-based event matching is an important problem in large-scale event-based publish/subscribe systems. However, open questions remain in analysis of its difficulty and evaluation of its solutions. This paper makes a few contributions toward analysis, evaluation and development of matching algorithms. First, based on a simplified yet generic model, we give a formal proof of hardness of matching problem by showing its equivalence to the notoriously hard Partial Match problem. Second, we compare two major existing matching approaches and show that counting-based algorithms are likely to be more computationally expensive than tree-based algorithms in this model. Third, we observe an important, prevalent characteristic of real-world publish/subscribe events, and develop a new matching algorithm called RAPIDMatch to exploit it. Finally, we propose a new metric for evaluation of matching algorithms. We analyze and evaluate RAPIDMatch using both the traditional and new metrics proposed. Results show that RAPIDMatch achieves large performance improvement over the tree-based algorithm under certain publish/subscribe scenarios.
Original language | English (US) |
---|---|
DOIs | |
State | Published - 2005 |
Event | 25th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS 2005 - Columbus, OH, United States Duration: Jun 6 2005 → Jun 10 2005 |
Conference
Conference | 25th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS 2005 |
---|---|
Country/Territory | United States |
City | Columbus, OH |
Period | 6/6/05 → 6/10/05 |
All Science Journal Classification (ASJC) codes
- Software
- Hardware and Architecture
- Computer Networks and Communications