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: 4229
Venue: SIGMOD
Year: 2010
Pagerank: 5.4187931e-05
Overall Rank: 5,589 | 61.16%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,249	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.132996e-05
6,524	Evaluation Strategies for Top-k Queries over Memory-Resident Inverted Indexes	2011	VLDB	5.0225949e-05
7,128	Scalable Social Coordination with Group Constraints using Enmeshed Queries	2013	CIDR	4.8181792e-05
8,583	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4859208e-05
9,245	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	4.3648789e-05
9,261	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB	4.3648789e-05

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
447	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00022927245
497	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00021667647
2,455	Optimizing Boolean Expressions in Object Bases	1992	VLDB	8.7667904e-05
2,951	Indexing Boolean Expressions	2009	VLDB	7.8248136e-05
3,355	Managing Expressions as Data in Relational Database Systems	2003	CIDR	7.1772076e-05
3,530	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB	7.0008977e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,722	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.9646931e-05
2,065	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6467359e-05
2,455	Optimizing Boolean Expressions in Object Bases	1992	VLDB	8.7667904e-05
5,722	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD	5.3534445e-05
6,249	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.132996e-05
5,637	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.3978567e-05
12,039	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1905499e-05
6,094	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2099705e-05
8,583	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4859208e-05
2,951	Indexing Boolean Expressions	2009	VLDB	7.8248136e-05