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: 10255
Venue: VLDB
Year: 2011
Pagerank: 8.7524354e-05
Overall Rank: 2,464 | 82.86%
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.8913631e-05
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
5,508	Fast Large-Scale Trajectory Clustering	2020	VLDB	5.4713696e-05
7,254	DEX: Query Execution in a Delta-based Storage System	2017	SIGMOD	4.7885915e-05
7,475	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD	4.7191809e-05
7,642	Bitlist: New Full-text Index for Low Space Cost and Efficient Keyword Search	2013	VLDB	4.6901822e-05
7,693	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	4.6759281e-05
8,156	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	4.5741172e-05
8,921	Leveraging Similarity Joins for Signal Reconstruction	2018	VLDB	4.427232e-05
8,927	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	4.427232e-05
9,173	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	4.3842827e-05
9,790	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	4.2818172e-05
11,693	Document Reordering for Faster Intersection	2019	VLDB	4.1945683e-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
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
1,124	Improving the Performance of List Intersection	2009	VLDB	0.00013847565

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
266	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029718727
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
8,156	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	4.5741172e-05
11,693	Document Reordering for Faster Intersection	2019	VLDB	4.1945683e-05
14,232	Stable Set and Multiset Operations in Optimal Time and Space	1988	PODS	-
3,490	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.0465856e-05
1,124	Improving the Performance of List Intersection	2009	VLDB	0.00013847565
250	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030661988
3,448	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.0844401e-05
4,353	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	6.263585e-05