Scalable event matching for overlapping subscriptions in pub/sub systems

Abstract

Content-based publish/subscribe systems allow matching the content of events with predicates in the subscriptions. However, most existing systems only allow a limited set of operators, such as comparison on primitive data types (string, integer, etc). In this paper, we consider a publish/subscribe system that supports more flexible events/subscriptions with the use of advanced, yet potentially expensive, matching operators. Examples of such operators are pattern recognizers on multimedia data and spatial operators on location data. We study a critical problem in these publish/subscribe systems, namely how to optimize the matching process for a large number of subscriptions. This is achieved by exploiting the overlap in the subscriptions and sharing the operator evaluation results whenever possible. We formulate the optimal subscription evaluation problem and show that it is NP-Hard. We propose an efficient d-approximation algorithm, where d is the maximum number of operators in one subscription, as well as a heuristic algorithm that can further improve the system performance in practice. Our experiment results show that the proposed algorithms can reduce the matching cost by up to 80%, as compared to a naive strategy that evaluates the subscriptions independently. © 2007 ACM.