A novel index structure to efficiently match events in large-scale publish/subscribe systems

The event matching algorithm, which checks the events against all the subscriptions, is a fundamental component of large-scale content-based publish/subscribe systems, and it is the key issue for improving the efficiency of the entire system. To meet the increasing efficiency requirements of real-time publish/subscribe systems, an event matching algorithm named PADEM (Pairwise Attribute Division based Event Matching) is presented in this paper. By dividing the attribute space into multiple pairwise attribute subspaces, PADEM constructs a novel index structure to classify all subscriptions in systems. This index structure can guarantee the matching process in its each unit can only be triggered by corresponding events. The experimental results demonstrate that PADEM can dramatically improve the efficiency of event matching, particularly in large-scale distributed systems with high volumes of subscriptions.