Fast Set Intersection in Memory

Summary: Linear-space in-memory set representations enable fast intersections. For k preprocessed sets of total size n, intersection runs in expected time O(n/√w + k r); a simpler variant favors practical speed with weaker guarantees, both beating state-of-the-art on synthetic and real workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10256
Venue: VLDB
Year: 2011
Pagerank: 8.7344475e-05
Overall Rank: 2,465 | 82.87%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Bolin Ding
2. Arnd Christian König

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 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
3,449	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0803234e-05
5,873	Fast Large-Scale Trajectory Clustering	2020	VLDB	5.2897929e-05
7,251	DEX: Query Execution in a Delta-based Storage System	2017	SIGMOD	4.7839943e-05
7,474	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD	4.7146619e-05
7,640	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	4.6859388e-05
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6714423e-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
8,930	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	4.4229886e-05
9,177	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	4.3800806e-05
9,793	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	4.2777144e-05
11,698	Document Reordering for Faster Intersection	2019	VLDB	4.1905499e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
1,121	Improving the Performance of List Intersection	2009	VLDB	0.00013838956

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
264	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029950264
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
8,160	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	4.5697316e-05
11,698	Document Reordering for Faster Intersection	2019	VLDB	4.1905499e-05
14,246	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS	-
3,461	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.0696567e-05
1,121	Improving the Performance of List Intersection	2009	VLDB	0.00013838956
248	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030888982
3,449	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0803234e-05
4,350	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.2576191e-05