Design of B+Tree-Based Predicate Index for Efficient Event Matching

摘要

Efficient event matching algorithms are the core of publish/subscribe systems. Such algorithms are typically designed based on memory structure for performance reasons. Given the explosive growth of information, it is not always practically feasible to keep the index for event filtering memory-resident, thereby necessitating the need for a secondary storage structure. Incidentally, even though search algorithms designed for active databases and spatio-temporal databases are applicable to publish/subscribe systems, these algorithms are not specifically designed for publish/subscribe systems which require both fast search as well as efficient support for dynamic insertions and deletions. To address this problem, we propose a predicate index for secondary storage structures with space complexity O(n) and search time complexity O(log n). Analytical comparison of our proposed algorithms with existing work indicates that our secondary storage predicate index is efficient for event matching.