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: h61905114cace7263
Venue: VLDB
Year: 2009
Pagerank: 9.7686642e-05
Overall Rank: 1,730 | 88.38%
DOI: 10.14778/1687627.1687722

Incoming Non-self Citations Over Time

Authors

1. Dimitris Tsirogiannis (University of Toronto)
2. Sudipto Guha (University of Pennsylvania)
3. Nick Koudas (University of Toronto)

BibTeX Citation

@article{tsirogiannis_vldb09,
        title = {{Improving the Performance of List Intersection}},
        author = {Tsirogiannis, Dimitris and Guha, Sudipto and Koudas, Nick},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687722},
        url = {https://doi.org/10.14778/1687627.1687722},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,653	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.969498e-05
1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.499042e-05
2,120	Fast Set Intersection in Memory	2011	VLDB	9.0077549e-05
2,977	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.7881518e-05
8,372	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	5.3434309e-05
9,261	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	5.2032182e-05
12,194	Document Reordering for Faster Intersection	2019	VLDB	4.9769913e-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
76	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00036891569
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033518428
110	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00032696785
223	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00024120979
253	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023047482
625	Adaptive Aggregation on Chip Multiprocessors	2007	VLDB	0.00015472161
1,041	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00012354465
1,434	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010663712
2,694	Executing Stream Joins on the Cell Processor	2007	VLDB	8.1197353e-05
2,750	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0569441e-05
2,760	BlogScope: A System for Online Analysis of High Volume Text Streams	2007	VLDB	8.0455704e-05
3,552	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD	7.2070901e-05
5,915	Inspector Joins	2005	VLDB	5.9472868e-05
6,825	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.6698066e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
2	2,038	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
3	3,552	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD
4	1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD
5	2,977	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB
6	6,426	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB
7	12,194	Document Reordering for Faster Intersection	2019	VLDB
8	1,653	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB
9	2,120	Fast Set Intersection in Memory	2011	VLDB
10	8,372	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB