A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions

Shuping Ji, Hans Arno Jacobsen

Research output: Contribution to journalConference articlepeer-review

6 Scopus citations

Abstract

Efficiently evaluating a large number of arbitrary Boolean expressions is needed in many applications such as advertising exchanges, complex event processing, and publish/subscribe systems. However, most solutions can support only conjunctive Boolean expression matching. The limited number of solutions that can directly work on arbitrary Boolean expressions present performance and flexibility limitations. Moreover, normalizing arbitrary Boolean expressions into conjunctive forms and then using existing methods for evaluating such expressions is not effective because of the potential exponential increase in the size of the expressions. Therefore, we propose the A-Tree data structure to efficiently index arbitrary Boolean expressions. A-Tree is a multirooted tree, in which predicates and subexpressions from different arbitrary Boolean expressions are aggregated and shared. A-Tree employs dynamic self-adjustment policies to adapt itself as the workload changes. Moreover, A-Tree adopts different event matching optimizations. Our comprehensive experiments show that A-Tree-based matching outperforms existing arbitrary Boolean expression matching algorithms in terms of memory use, matching time, and index construction time by up to 71%, 99% and 75%, respectively. Even on conjunctive expression workloads, A-Tree achieves a lower matching time than state-of-the-art conjunctive expression matching algorithms.

Original languageEnglish
Pages (from-to)817-829
Number of pages13
JournalProceedings of the ACM SIGMOD International Conference on Management of Data
DOIs
StatePublished - 2021
Externally publishedYes
Event2021 International Conference on Management of Data, SIGMOD 2021 - Virtual, Online, China
Duration: 20 Jun 202125 Jun 2021

Keywords

  • algorithm
  • arbitrary boolean expressions
  • complex event processing
  • data structure
  • publish/subscribe

Fingerprint

Dive into the research topics of 'A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions'. Together they form a unique fingerprint.

Cite this