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: 11801
Venue: VLDB
Year: 2019
Pagerank: 4.5741172e-05
Overall Rank: 8,156 | 43.27%
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,366	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3493859e-05
10,314	Index Intersection for High-Dimensional Range Queries	2026	VLDB	4.1945683e-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.00022734812
1,124	Improving the Performance of List Intersection	2009	VLDB	0.00013847565
2,464	Fast Set Intersection in Memory	2011	VLDB	8.7524354e-05
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
4,838	Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers	2014	VLDB	5.8887949e-05
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6759281e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,826	Optimizing Result Prefetching in Web Search Engines with Segmented Indices	2002	VLDB	5.8943133e-05
7,642	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	4.6901822e-05
3,091	Optimized Query Execution in Large Search Engines with Global Page Ordering	2003	VLDB	7.5805947e-05
6,461	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.0538774e-05
11,595	Minimization of Classifier Construction Cost for Search Queries	2020	SIGMOD	4.1945683e-05
1,517	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD	0.00011578859
2,464	Fast Set Intersection in Memory	2011	VLDB	8.7524354e-05
2,051	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.686731e-05
1,124	Improving the Performance of List Intersection	2009	VLDB	0.00013847565
11,693	Document Reordering for Faster Intersection	2019	VLDB	4.1945683e-05