BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space
Mohammad Sadoghi and Hans-Arno Jacobsen.
In 37th SIGMOD International Conference on Management of Data (SIGMOD), pages 637-648, June 2011.
(Winner of EPTS Innovative Principle Award 2011).
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
Tags: content-based matching, content-based publish/subscribe, event processing, publish/subscribe
Readers who enjoyed the above work, may also like the following:
- Location-based Matching in Publish/Subscribe Revisited.
Mohammad Sadoghi and Hans-Arno Jacobsen. In ACM/IFIP/USENIX 13th International Conference on Middleware, 2012.
Tags: content-based matching, content-based publish/subscribe, publish/subscribe, event processing
- Expressive Location-based Continuous Query Evaluation With Binary Decision Diagrams.
Zhengdao Xu and Hans-Arno Jacobsen. In IEEE International Conference on Data Engineering (ICDE), pages 1155-1158, March 2009. Acceptance rate: 27 %. Number of submissions: 554.
Tags: algorithms, bdd, content-based matching, content-based publish/subscribe, event processing, topss, publish/subscribe, spatial query, location-based services
- Modelling Performance Optimizations for Content-based Publish/Subscribe.
Alex Wun and Hans-Arno Jacobsen. In DEBS 2007, pages 171-179, Toronto, Canada, June 2007.
Tags: content-based matching, content-based publish/subscribe, event processing, padres, publish/subscribe, topss, algorithms
|