DEXIN: A fast content-based multi-attribute event matching algorithm using dynamic exclusive and inclusive methods

摘要

Event matching acts as a key role in publish/subscribe services, which takes charge of finding all subscriptions that match an event from a subscription set. In large content-based multi-attribute publish/subscribe systems, the performance of event matching is severely challenged due to the increased system scale and search complexity. Most existing event matching algorithms cannot effectively sustain in such a scenario. In this paper, we propose DEXIN (Dynamic Exclusive and INclusive), a fast content-based multi-attribute event matching algorithm using dynamic exclusive and inclusive methods. DEXIN supports highly efficient event matching for subscriptions with limited range-based, unlimited range-based and point-based constraints. DEXIN prepares a pipelined event matching process optimized for each incoming event. The exclusive and inclusive methods, which have different matching costs, are dynamically chosen for event matching over a single attribute. Thus, the search space shrinks very fast since non-matched subscriptions can be filtered out by DEXIN at very early stages in the pipeline. The experiment results demonstrate that DEXIN is superior to several state-of-the-art reference algorithms. Especially, the leading advantage of DEXIN is more significant on matching time and stability for large number of subscriptions and attributes in multiple scenarios.