Analysis and optimization for boolean expression indexing

Mohammad Sadoghi, Hans Arno Jacobsen

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

BE-Tree is a novel dynamic data structure designed to efficiently index Boolean expressions over a highdimensional discrete space. BE-Tree copes with both high-dimensionality and expressiveness of Boolean expressions by introducing an effective 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. 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 finite 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 cospaces, profile 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.

Original languageEnglish
Article number8
JournalACM Transactions on Database Systems
Volume38
Issue number2
DOIs
StatePublished - Jun 2013
Externally publishedYes

Keywords

  • Boolean expressions
  • Complex event processing
  • Data structure
  • Publish/subscribe

Fingerprint

Dive into the research topics of 'Analysis and optimization for boolean expression indexing'. Together they form a unique fingerprint.

Cite this