HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Efficient Matching Algorithms for Publish and Subscribe Systems

Abstract : Publish/Subscribe is the paradigm in which users express long-term interests («subscriptions») and some external agent (perhaps other users) «publishes» events (e.g., offers). The job of Publish/Subscribe software is to send events to the owners of subscriptions satisfied by those events. For example, a user subscription may consist of an interest in an airplane of a certain type, not to exceed a certain price. A published event may consist of an offer of an airplane with certain properties including price. A subscriptio- n closely resembles a trigger in that it is a long-lived conditional query associated with an action (usually, informing the subscriber). However, it is less general than a trigger so novel data structures and implementations may enable the creation of scalable, high performance publish-subscribe systems. This paper describes an attempt at the construction of such algorithm- s and its implementation. Using a combination of data structures, application-- specific caching policies, and application-specific query processing our system can handle 600 events per second on 6 million subscriptions consisting of conjunctions of (attribute, comparison operator, value) predicates.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:14:48 AM
Last modification on : Thursday, February 3, 2022 - 11:18:35 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:12:43 PM


  • HAL Id : inria-00072544, version 1



Françoise Fabret, François Llirbat, Arno Jacobsen, Joâo Pereira, Kenneth Ross, et al.. Efficient Matching Algorithms for Publish and Subscribe Systems. [Research Report] RR-4089, INRIA. 2000. ⟨inria-00072544⟩



Record views


Files downloads