A unified approach to routing, covering and merging in publish/subscribe systems based on modified binary decision diagrams

The challenge faced by content-based publish/subscribe systems is the ability to handle a vast amount of dynamic information with limited system resources. In current p/s systems, each subscription is processed in isolation. Neither relationships among individual subscriptions are exploited, nor historic information about subscriptions and publications is taken into account. We believe that this neglect limits overall system efficiency. In this paper, we represent subscriptions using modified binary decision diagrams (MBDs), and design an index data structure to maintain distinct predicates and manage associated Boolean variables. Our MBD-based approach can address, in a unified way, publication routing and subscription/advertisement covering and merging. We propose a novel covering algorithm based on MBDs. The algorithm can take historic information about subscription and publication populations into account and exploits relations between subscriptions. We explore merging, especially imperfect merging, and discuss an advertisement-based optimization applicable to subscription merging.