Indexing Boolean Expressions

Steven Whang, Chad Brower, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Ramana Yerneni, Hector Garcia-Molina

TL;DR

This paper introduces a novel method for efficiently indexing and querying complex Boolean expressions (both DNF and CNF) over high-dimensional, multi-valued attribute spaces. By leveraging inverted lists, traditionally used in information retrieval, they achieve significant performance improvements for applications like online advertising and publish/subscribe systems, especially when dealing with complex expressions and the need for ranked results.

What Problem Does This Paper Address?

The paper tackles the challenge of efficiently finding Boolean expressions (BEs) that are satisfied by a given set of attribute-value assignments. This is crucial for applications like online advertising, where advertisers define targeting criteria as BEs and users' profiles are represented by attribute assignments, or in publish/subscribe systems where users subscribe to events defined by BEs. Existing solutions struggle with the complexity of general DNF and CNF expressions, especially when dealing with multi-valued attributes and the presence of NOT operators. They often only support simpler forms of expressions or require post-processing for complex cases, leading to performance bottlenecks.

Methods

The core of the proposed solution lies in adapting the inverted list data structure, commonly used in information retrieval, for indexing Boolean expressions.

  • DNF Algorithm: DNF expressions are first broken down into their constituent conjunctions. An inverted list is then built where each key (attribute-value pair) maps to a posting list containing IDs of conjunctions that include that key. The algorithm efficiently identifies matching conjunctions by intersecting relevant posting lists.
  • CNF Algorithm: Similar to the DNF approach, CNF expressions are indexed. However, the CNF algorithm needs to ensure that all disjunctions within a CNF are satisfied. This involves more complex counter management to track the satisfaction of each disjunction.
  • Ranking: A key innovation is the ability to efficiently return the top-N matching BEs based on a defined scoring mechanism. This is achieved by incorporating scoring and pruning techniques into the DNF and CNF algorithms, leveraging upper bounds of scores to avoid unnecessary computations.
  • Handling Complexities: The authors address multi-valued attributes (using the ∈ operator) and negation (using the £ operator), and introduce mechanisms to handle weak and strong negation predicates. They also discuss how range predicates can be converted into ∈ and £ predicates for unified processing.

Datasets

The authors used synthetic datasets generated from statistics of real display advertising contracts. These datasets were designed to mimic real-world scenarios with varying numbers of BEs, DNF/CNF sizes, dimensions (attributes), and selectivity (match probability). They also used a subset of 1 million real display advertising adlogs for assignments.

Key Insights and Ideas

  • Inverted Lists for BEs: The most significant insight is that inverted lists, despite their traditional use for document retrieval, can be effectively adapted to index and query complex Boolean expressions. This leverages their inherent scalability and efficiency for read-heavy workloads.
  • Top-N Ranking: The ability to efficiently retrieve ranked results is a crucial extension. By integrating scoring and pruning, the system can provide the "best" matching BEs, which is vital for applications with limited display real estate or where user experience is paramount.
  • Unified Handling of DNF/CNF: The paper presents a unified framework that can handle both DNF and CNF expressions, which is a significant advantage over existing methods that often specialize in one form.
  • Handling Multi-valued Attributes and Negation: The proposed approach effectively handles the complexities of multi-valued attributes and negation, which are common in real-world targeting and subscription scenarios.

Key Results

  • Performance Improvements: The proposed DNF algorithm was shown to be significantly faster than existing methods like Le Subscribe and SIFT, especially for complex expressions, high dimensions, and large numbers of BEs. For instance, it was 11.2 to 20.9 times faster than SIFT in some scenarios.
  • Scalability: The algorithms demonstrated excellent scalability, handling up to 1 million BEs efficiently. The DNF algorithm showed better scalability with increasing BE size compared to Le Subscribe.
  • Ranking Efficiency: The ranking algorithms provided performance improvements over a naive approach, with the CNF ranking algorithm showing significant speedups (35-45%) due to more opportunities for pruning.
  • CNF Performance: The CNF algorithm outperformed PSCAN and SCAN by 1.9-2.6x and 10.5-12.7x, respectively.

Limitations and Future Work

  • Update Mechanism: While the paper mentions adapting techniques for handling updates (maintaining a small "tail" data structure), a detailed discussion of the update mechanism's performance and complexity is not provided.
  • Scoring Method: The paper focuses on the efficiency of retrieving top-N BEs given a scoring method, rather than proposing novel scoring functions. The effectiveness of the ranking is dependent on the quality of the scoring.
  • Low-Dimension Performance: The DNF algorithm's performance advantage over Le Subscribe (specifically the Propagation algorithm) was more pronounced in high-dimensional settings. The authors suggest that other clustering algorithms within Le Subscribe might perform better in low-dimensional scenarios.
  • Future Work: The authors suggest further exploration of efficient update mechanisms and the development of more sophisticated scoring functions for ranking. They also note that the "best" hierarchy for converting range predicates is a separate area of interest.

Summary updated

BibTeX
@article{whang2009indexing,
  author = {Steven Whang and Chad Brower and Jayavel Shanmugasundaram and Sergei Vassilvitskii and Erik Vee and Ramana Yerneni and Hector Garcia-Molina},
  title = {{Indexing Boolean Expressions}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687633},
}
Figure