ACM Transactions on Database Systems (TODS), 38(2), June 2013.
BE-Tree is a novel dynamic data structure designed to efï¬ciently index Boolean expressions over a high-dimensional discrete space. BE-Tree copes with both high-dimensionality and expressiveness of Boolean expressions by introducing an effective two-phase space-cutting technique that speciï¬cally utilizes the discrete and ï¬nite domain properties of the space. Furthermore, BE-Tree employs self-adjustment policies to dynamically adapt the tree as the workload changes. Moreover, in BE-Tree, we develop two novel cache-conscious predicate evaluation techniques, namely, lazy and bitmap evaluations, that
also exploit the underlying discrete and ï¬nite space to substantially reduce BE-Treeâ€™s matching time by up to 75%.
BE-Tree is a general index structure for matching Boolean expression which has a wide range of applications including (complex) event processing, publish/subscribe matching, emerging applications in co-spaces, proï¬le matching for targeted web advertising, and approximate string matching. Finally, the superiority of BE-Tree is proven through a comprehensive evaluation with state-of-the-art index structures designed for matching Boolean expressions