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: 10168
Venue: VLDB
Year: 2009
Pagerank: 9.9327227e-05
Overall Rank: 1,717 | 88.23%
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,655	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	0.00010103504
2,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1514258e-05
2,245	Fast Set Intersection in Memory	2011	VLDB	8.8734284e-05
3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.6328776e-05
8,201	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	5.467444e-05
9,076	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	5.3251649e-05
11,888	Document Reordering for Faster Intersection	2019	VLDB	5.093636e-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
74	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00037330605
105	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033877899
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
215	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00024507963
261	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023097188
632	Adaptive Aggregation on Chip Multiprocessors	2007	VLDB	0.00015575286
1,028	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00012557617
1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010890603
2,655	Executing Stream Joins on the Cell Processor	2007	VLDB	8.2888851e-05
2,703	BlogScope: A System for Online Analysis of High Volume Text Streams	2007	VLDB	8.2340288e-05
2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	8.2108958e-05
3,524	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD	7.3448437e-05
5,829	Inspector Joins	2005	VLDB	6.073697e-05
6,699	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB	5.7982932e-05

Semantically Similar Papers

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