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.6869284e-05
Overall Rank: 1,769 | 88.11%
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,671	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.9310625e-05
2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1750421e-05
2,316	Fast Set Intersection in Memory	2011	VLDB	8.6496494e-05
3,289	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.4528818e-05
8,368	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	5.3459616e-05
9,251	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	5.2056825e-05
12,188	Document Reordering for Faster Intersection	2019	VLDB	4.9793485e-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.00036898845
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033526937
110	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00032700879
223	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.0002412513
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023050233
626	Adaptive Aggregation on Chip Multiprocessors	2007	VLDB	0.00015473276
1,041	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00012356709
1,434	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010665845
2,696	Executing Stream Joins on the Cell Processor	2007	VLDB	8.1205649e-05
2,750	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.0573403e-05
2,760	BlogScope: A System for Online Analysis of High Volume Text Streams	2007	VLDB	8.0493804e-05
3,584	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD	7.1896153e-05
5,922	Inspector Joins	2005	VLDB	5.9469659e-05
6,829	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.6696028e-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,035	Incremental Updates of Inverted Lists for Text Document Retrieval	1994	SIGMOD
3	3,584	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD
4	2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD
5	3,289	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB
6	6,434	An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors	2018	VLDB
7	12,188	Document Reordering for Faster Intersection	2019	VLDB
8	1,671	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB
9	2,316	Fast Set Intersection in Memory	2011	VLDB
10	8,368	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB