Indexing Boolean Expressions

Summary: Inverted-list index for arbitrary DNF/CNF expressions over multi-valued attributes, including NOTs. Enables top-N matching via inverted-list ranking, boosting online advertising and publish/subscribe workloads; shows dramatic performance gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9950
Venue: VLDB
Year: 2009
Pagerank: 7.8340452e-05
Overall Rank: 2,949 | 79.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,545	SKYPE: Top-k Spatial-keyword Publish/Subscribe Over Sliding Window	2016	VLDB	6.0995026e-05
4,950	Evaluating Temporal Queries Over Video Feeds	2021	SIGMOD	5.8104133e-05
5,582	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	5.4241353e-05
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
6,992	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	4.8701339e-05
7,120	Location-Aware Pub/Sub System: When Continuous Moving Queries Meet Dynamic Event Streams	2015	SIGMOD	4.8260729e-05
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6759281e-05
8,277	TQVS: Temporal Queries over Video Streams in Action	2020	SIGMOD	4.5436203e-05
8,587	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4902253e-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
259	High-Performance Complex Event Processing over Streams	2006	SIGMOD	0.00030174924
500	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00021637423
3,212	Cayuga: A High-Performance Event Processing Engine	2007	SIGMOD	7.3730439e-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
5,391	Scalable Ranked Publish/Subscribe	2008	VLDB	5.533552e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,109	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	4.8292998e-05
9,322	Indexing for Keyword Search with Structured Constraints	2023	PODS	4.3556432e-05
2,171	Selectivity Estimation For Boolean Queries	2000	PODS	9.3807165e-05
6,243	BE-Tree: An Index Structure to Efficiently Match Boolean Expressions over High-dimensional Discrete Space	2011	SIGMOD	5.1402191e-05
9,254	PS-Tree-Based Efficient Boolean Expression Matching for High-Dimensional and Dense Workloads	2019	VLDB	4.3690661e-05
7,522	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7180617e-05
12,099	Efficient Indexing for Diverse Query Results	2013	VLDB	4.1945683e-05
6,992	An Efficient Publish/Subscribe Index for E-Commerce Databases	2014	VLDB	4.8701339e-05
8,587	A-Tree: A Dynamic Data Structure for Efficiently Indexing Arbitrary Boolean Expressions	2021	SIGMOD	4.4902253e-05
5,582	Efficiently Evaluating Complex Boolean Expressions	2010	SIGMOD	5.4241353e-05