file.pdf (167.07 kB)

Efficient Filtering in Publish-Subscribe Systems using Binary Decision Diagrams

Download (167.07 kB)
journal contribution
posted on 01.01.1985 by Alexis Campailla, Sagar Chaki, Edmund M Clarke, Somesh Jha, Helmut Veith
Implicit invocation or publish-subscribe has become an important architectural style for large-scale system design and evolution. The publish-subscribe style facilitates developing large-scale systems by composing separately developed components because the style permits loose coupling between various components. One of the major bottlenecks in using publish-subscribe systems for very large scale systems is the efficiency of filtering incoming messages, i.e., matching of published events with event subscriptions. This is a very challenging problem because in a realistic publishsubscribe system the number of subscriptions can be large. In this paper we present an approach for matching published events with subscriptions which scales to a large number of subscriptions. Our approach uses Binary Decision Diagrams, a compact data structure for representing boolean functions which has been successfully used in verification techniques such as model checking. Experimental results clearly demonstrate the efficiency of our approach.

History

Publisher Statement

All Rights Reserved

Date

01/01/1985

Exports

Exports