Fast Set Intersection in Memory

Summary: Linear-space set representations enable k-way intersection in expected O(n/√w + kr) time, exploiting word-level parallelism. A simpler practical variant and the optimal-style algorithm outperform existing methods on synthetic and real workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10446
Venue: VLDB
Year: 2011
Pagerank: 8.8734284e-05
Overall Rank: 2,245 | 84.60%
DOI: 10.14778/1938545.1938548

Incoming Non-self Citations Over Time

Authors

1. Bolin Ding (University of Illinois Urbana-Champaign)
2. Arnd Christian König (Microsoft)

BibTeX Citation

@article{ding_vldb11,
        title = {{Fast Set Intersection in Memory}},
        author = {Ding, Bolin and König, Arnd Christian},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {4},
        pages = {255--266},
        doi = {10.14778/1938545.1938548},
        url = {https://doi.org/10.14778/1938545.1938548},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1514258e-05
3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.6328776e-05
5,112	Fast Large-Scale Trajectory Clustering	2020	VLDB	6.3596697e-05
7,300	DEX: Query Execution in a Delta-based Storage System	2017	SIGMOD	5.6509215e-05
7,629	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	5.5786605e-05
7,842	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.5333985e-05
7,896	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD	5.5201308e-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
9,082	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	5.3251649e-05
9,176	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	5.3081996e-05
9,944	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	5.1915905e-05
11,888	Document Reordering for Faster Intersection	2019	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
1,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	169	Efficient Exact Set-Similarity Joins	2006	VLDB
2	1,561	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
3	8,201	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB
4	11,888	Document Reordering for Faster Intersection	2019	VLDB
5	14,432	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS
6	3,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
7	1,717	Improving the Performance of List Intersection	2009	VLDB
8	200	Efficient set joins on similarity predicates	2004	SIGMOD
9	3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB
10	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD