List Intersection for Web Search: Algorithms, Cost Models, and Optimizations

Summary: Cost-based optimization over a space of list-intersection algorithms and combinations for web-search postings. Hardware-aware cost model selects low-cost plans, often mixing 2-way strategies to beat 2-way and k-way baselines, outperforming state-of-the-art alternatives; validated on two CPUs with real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11802
Venue: VLDB
Year: 2019
Pagerank: 4.5697316e-05
Overall Rank: 8,160 | 43.29%
DOI: 10.14778/3275536.3275537

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,375	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3452177e-05
10,326	Index Intersection for High-Dimensional Range Queries	2026	VLDB	4.1905499e-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
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
1,121	Improving the Performance of List Intersection	2009	VLDB	0.00013838956
2,465	Fast Set Intersection in Memory	2011	VLDB	8.7344475e-05
3,449	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0803234e-05
4,838	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	5.883146e-05
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6714423e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,847	Optimizing Result Prefetching in Web Search Engines with Segmented Indices	2002	VLDB	5.8724638e-05
7,640	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	4.6859388e-05
3,097	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB	7.5745942e-05
6,441	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.0546366e-05
11,599	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1905499e-05
1,514	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD	0.00011571661
2,465	Fast Set Intersection in Memory	2011	VLDB	8.7344475e-05
2,046	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.6922338e-05
1,121	Improving the Performance of List Intersection	2009	VLDB	0.00013838956
11,698	Document Reordering for Faster Intersection	2019	VLDB	4.1905499e-05