In 37th SIGMOD International Conference on Management of Data (SIGMOD), pages 637-648, June 2011.
(Winner of EPTS Innovative Principle Award 2011).
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.