Improving the Performance of List Intersection

Summary: Optimizes list-intersection for arbitrary k lists on modern hardware: Dynamic Probes (runtime adaptive probing) and Quantile-based (precomputed order) for sorted lists; unsorted lists use a hash-based method. Empirical evaluation on eight-core CMPs with real and synthetic data demonstrates practical speedups for data-management workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9977
Venue: VLDB
Year: 2009
Pagerank: 0.00013847565
Overall Rank: 1,124 | 92.19%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,973	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.8913631e-05
2,051	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.686731e-05
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
8,156	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	4.5741172e-05
8,921	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	4.427232e-05
11,693	Document Reordering for Faster Intersection	2019	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
81	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00055548574
84	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00053866006
124	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00045103515
145	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.0004138408
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
714	Adaptive Aggregation on Chip Multiprocessors	2007	VLDB	0.00017730584
1,101	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00014070632
1,566	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00011343771
2,166	BlogScope: A System for Online Analysis of High Volume Text Streams	2007	VLDB	9.3896206e-05
2,763	Executing Stream Joins on the Cell Processor	2007	VLDB	8.1579306e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
3,717	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD	6.8210203e-05
5,166	Inspector Joins	2005	VLDB	5.6521853e-05
6,174	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.1696569e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
1,517	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD	0.00011578859
3,717	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD	6.8210203e-05
1,973	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.8913631e-05
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
6,461	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB	5.0538774e-05
11,693	Document Reordering for Faster Intersection	2019	VLDB	4.1945683e-05
2,051	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.686731e-05
2,464	Fast Set Intersection in Memory	2011	VLDB	8.7524354e-05
8,156	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	4.5741172e-05