DBScholar

Back to papers

Efficiently Evaluating Complex Boolean Expressions

Summary: Bottom-up evaluation of Boolean expressions avoids CNF/DNF blow-up, reusing conjunctions and pruning irrelevant subexpressions. Two techniques: Dewey-ID indexing and interval-mapping; restrict evaluation to relevant subexpressions; ad-exchange data show scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
4290
Venue
SIGMOD
Year
2010
Pagerank
6.3216824e-05
Overall Rank
5,199 | 64.34%
DOI
10.1145/1807167.1807171

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{fontoura_sigmod10,
        title = {{Efficiently Evaluating Complex Boolean Expressions}},
        author = {Fontoura, Marcus and Sadanandan, Suhas and Shanmugasundaram, Jayavel and Vassilvitski, Sergei and Vee, Erik and Venkatesan, Srihari and Zien, Jason},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807171},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807171},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank Citing Paper Year Venue Pagerank
6,016 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD 6.0082425e-05
6,552 Evaluation Strategies for Top-k Queries over Memory-Resident Inverted Indexes 2011 VLDB 5.8425759e-05
7,644 Scalable Social Coordination with Group Constraints using Enmeshed Queries 2013 CIDR 5.5763131e-05
8,577 A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions 2021 SIGMOD 5.409313e-05
8,893 Optimizing Disjunctive Queries with Tagged Execution 2024 SIGMOD 5.3504579e-05
9,400 PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads 2019 VLDB 5.2755515e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
362 Storing and Querying Ordered XML Using a Relational Database System 2002 SIGMOD 0.00020125068
441 Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems 2001 SIGMOD 0.00018407547
2,739 Indexing Boolean Expressions 2009 VLDB 8.1872509e-05
2,923 Optimizing Boolean Expressions in Object Bases 1992 VLDB 7.9578414e-05
3,414 Managing Expressions as Data in Relational Database Systems 2003 CIDR 7.4313224e-05
3,742 RE-Tree: An Efficient Index Structure for Regular Expressions 2002 VLDB 7.1577657e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 4,301 Read-Once Functions and Query Evaluation in Probabilistic Databases 2010 VLDB
2 1,894 Optimizing Queries On Compressed Bitmaps 2000 VLDB
3 2,923 Optimizing Boolean Expressions in Object Bases 1992 VLDB
4 6,150 Flexible and Efficient XML Search with Complex Full-Text Predicates 2006 SIGMOD
5 6,016 BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space 2011 SIGMOD
6 6,729 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB
7 12,229 The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity 2013 PODS
8 6,072 Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited 1989 SIGMOD
9 8,577 A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions 2021 SIGMOD
10 2,739 Indexing Boolean Expressions 2009 VLDB