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: 4228
Venue: SIGMOD
Year: 2010
Pagerank: 5.4241353e-05
Overall Rank: 5,582 | 61.17%
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,243	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.1402191e-05
6,527	Evaluation Strategies for Top-k Queries over Memory-Resident Inverted Indexes	2011	VLDB	5.0257582e-05
7,129	Scalable Social Coordination with Group Constraints using Enmeshed Queries	2013	CIDR	4.8228141e-05
8,587	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4902253e-05
9,238	Optimizing Disjunctive Queries with Tagged Execution	2024	SIGMOD	4.3690661e-05
9,254	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB	4.3690661e-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
446	Storing and Querying Ordered XML Using a Relational Database System	2002	SIGMOD	0.00022925415
500	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00021637423
2,455	Optimizing Boolean Expressions in Object Bases	1992	VLDB	8.7770449e-05
2,949	Indexing Boolean Expressions	2009	VLDB	7.8340452e-05
3,353	Managing Expressions as Data in Relational Database Systems	2003	CIDR	7.1843143e-05
3,526	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB	7.0078308e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,720	Read-Once Functions and Query Evaluation in Probabilistic Databases	2010	VLDB	5.973811e-05
2,061	Optimizing Queries On Compressed Bitmaps	2000	VLDB	9.6529345e-05
2,455	Optimizing Boolean Expressions in Object Bases	1992	VLDB	8.7770449e-05
5,712	Flexible and Efficient XML Search with Complex Full-Text Predicates	2006	SIGMOD	5.3584486e-05
6,243	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.1402191e-05
5,628	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.4030815e-05
12,031	The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity	2013	PODS	4.1945683e-05
6,090	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2148332e-05
8,587	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4902253e-05
2,949	Indexing Boolean Expressions	2009	VLDB	7.8340452e-05