Efficient matching for state-persistent publish/subscribe systems

Content-based publish/subscribe systems allow information dissemination and fine-grained information filtering in loosely coupled distributed systems. Stateless publish/subscribe systems send notifications to all subscribers whose subscriptions match an incoming publication. State-persistent publish/subscribe systems, a recently proposed model that stores the states of both publications and subscriptions, only send notifications upon state transitions. The information filtering process requires an efficient matching algorithm with high throughput and scalability. Although there have been studies on matching algorithms for stateless publish/subscribe systems, the matching problem for state-persistent publish/subscribe systems is still an open research problem. This paper presents a novel content-based matching algorithm and its data structures for state-persistent publish/subscribe systems. We will also present the complexity analysis and results of simulations that validates the analytical predictions.