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)
Incoming Non-self Citations Over Time
Authors
- 1. Marcus Fontoura (Yahoo)
- 2. Suhas Sadanandan (Yahoo)
- 3. Jayavel Shanmugasundaram (Yahoo)
- 4. Sergei Vassilvitski (Yahoo)
- 5. Erik Vee (Yahoo)
- 6. Srihari Venkatesan (Yahoo)
- 7. Jason Zien (Yahoo)
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,143 | BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space | 2011 | SIGMOD | 5.8706533e-05 |
| 6,680 | Evaluation Strategies for Top-k Queries over Memory-Resident Inverted Indexes | 2011 | VLDB | 5.708948e-05 |
| 7,791 | Scalable Social Coordination with Group Constraints using Enmeshed Queries | 2013 | CIDR | 5.4506612e-05 |
| 8,753 | A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions | 2021 | SIGMOD | 5.2854393e-05 |
| 9,060 | Optimizing Disjunctive Queries with Tagged Execution | 2024 | SIGMOD | 5.227932e-05 |
| 9,590 | PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads | 2019 | VLDB | 5.154741e-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 |
|---|---|---|---|---|
| 374 | Storing and Querying Ordered XML Using a Relational Database System | 2002 | SIGMOD | 0.00019698564 |
| 451 | Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems | 2001 | SIGMOD | 0.00018017347 |
| 2,793 | Indexing Boolean Expressions | 2009 | VLDB | 8.0017712e-05 |
| 2,984 | Optimizing Boolean Expressions in Object Bases | 1992 | VLDB | 7.780464e-05 |
| 3,486 | Managing Expressions as Data in Relational Database Systems | 2003 | CIDR | 7.2613516e-05 |
| 3,830 | RE-Tree: An Efficient Index Structure for Regular Expressions | 2002 | VLDB | 6.9940102e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,390 | Read-Once Functions and Query Evaluation in Probabilistic Databases | 2010 | VLDB |
| 2 | 1,932 | Optimizing Queries On Compressed Bitmaps | 2000 | VLDB |
| 3 | 2,984 | Optimizing Boolean Expressions in Object Bases | 1992 | VLDB |
| 4 | 6,276 | Flexible and Efficient XML Search with Complex Full-Text Predicates | 2006 | SIGMOD |
| 5 | 6,143 | BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space | 2011 | SIGMOD |
| 6 | 6,875 | Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries | 1990 | VLDB |
| 7 | 12,526 | The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity | 2013 | PODS |
| 8 | 6,198 | Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited | 1989 | SIGMOD |
| 9 | 8,753 | A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions | 2021 | SIGMOD |
| 10 | 2,793 | Indexing Boolean Expressions | 2009 | VLDB |