Efficient Filtering in Publish-Subscribe Systems using Binary Decision Diagrams
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 publish-subscribe
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.
Download:[PS,PDF]
Somesh Jha
Last modified: Fri Apr 11 16:18:26 CDT 2003