Database Paper Browser

Back to papers

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
9978
Venue
VLDB
Year
2009
Pagerank
0.00013838956
Overall Rank
1,121 | 92.22%
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.8834701e-05
2,046 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.6922338e-05
2,465 Fast Set Intersection in Memory 2011 VLDB 8.7344475e-05
3,449 Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions 2015 VLDB 7.0803234e-05
8,160 List Intersection for Web Search: Algorithms, Cost Models, and Optimizations 2019 VLDB 4.5697316e-05
8,924 Leveraging Similarity Joins for Signal Reconstruction 2018 VLDB 4.4229886e-05
11,698 Document Reordering for Faster Intersection 2019 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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.00055253195
85 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053652634
124 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.0004501099
145 Quickly Generating Billion-Record Synthetic Databases 1994 SIGMOD 0.00041403894
274 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029383266
711 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00017724982
1,100 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00014062265
1,561 Power-Conserving Computation of Order-Statistics over Sensor Networks 2004 PODS 0.00011349345
2,171 BlogScope: A System for Online Analysis of High Volume Text Streams 2007 VLDB 9.3805639e-05
2,768 Executing Stream Joins on the Cell Processor 2007 VLDB 8.1518597e-05
2,952 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS 7.8230109e-05
3,699 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 6.827026e-05
5,165 Inspector Joins 2005 VLDB 5.6477024e-05
6,176 Percentile Finding Algorithm for Multiple Sorted Runs 1989 VLDB 5.1650962e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
350 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00026368305
1,514 Incremental Updates of Inverted Lists for Text Document Retrieval 1994 SIGMOD 0.00011571661
3,699 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 6.827026e-05
1,973 Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions 2018 SIGMOD 9.8834701e-05
3,449 Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions 2015 VLDB 7.0803234e-05
6,441 An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors 2018 VLDB 5.0546366e-05
11,698 Document Reordering for Faster Intersection 2019 VLDB 4.1905499e-05
2,046 Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units 2011 VLDB 9.6922338e-05
2,465 Fast Set Intersection in Memory 2011 VLDB 8.7344475e-05
8,160 List Intersection for Web Search: Algorithms, Cost Models, and Optimizations 2019 VLDB 4.5697316e-05