Analysis and algorithms for content-based event matching

Satyen Kale, Elad Hazan, Fengyun Cao, Jaswinder Pal Singh

Research output: Contribution to conferencePaperpeer-review

23 Scopus citations

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 languageEnglish (US)
DOIs
StatePublished - 2005
Event25th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS 2005 - Columbus, OH, United States
Duration: Jun 6 2005Jun 10 2005

Conference

Conference25th IEEE International Conference on Distributed Computing Systems Workshops, ICDCS 2005
Country/TerritoryUnited States
CityColumbus, OH
Period6/6/056/10/05

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Analysis and algorithms for content-based event matching'. Together they form a unique fingerprint.

Cite this