Middleware Systems Research Group

University of Toronto, Canada

• << Publications

BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space

Abstract

BE-Tree is a novel dynamic tree structure designed to efficiently index Boolean expressions over a high-dimensional discrete space. BE-Tree copes with both high-dimensionality and expressiveness of Boolean expressions by introducing a novel two-phase space cutting technique that specifically utilizes the discrete and finite domain properties of the space. Furthermore, BE-Tree employs self-adjustment policies to dynamically adapt the tree as the workload changes. We conduct a comprehensive evaluation to demonstrate the superiority of the BE-Tree in comparison with state-of-the-art index structures designed for matching Boolean expressions.

**The results in this paper were verified by the SIGMOD repeatability committee.**

***Winner of Event Processing Technical Society (EPTS) Innovative Principle Award 2011.***

Download

Related Projects

• Extensible Efficient Event Processing Kernel (E^3-Kernel)
• Boolean Expression Tree (BE-Tree)
• Federated Publish/Subscribe (PADRES)
• Toronto Publish/Subscribe System Family (ToPSS)

Tags: content-based matching, content-based publish/subscribe, event processing, publish/subscribe