Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions

Summary: Introduces a branch-misprediction-resilient SIMD algorithm for intersecting sorted arrays, comparing blocks of elements and advancing pointers multiple positions. It requires no preprocessing and beats gcc’s std::set_intersection by up to 5.2× on Xeon/POWER7+. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: he926386c02a3652a
Venue: VLDB
Year: 2015
Pagerank: 7.7881518e-05
Overall Rank: 2,977 | 80.00%
DOI: 10.14778/2735508.2735516
PDF: Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

1. Hiroshi Inoue (IBM)
2. Moriyoshi Ohara (IBM)
3. Kenjiro Taura (University of Tokyo)

BibTeX Citation

@article{inoue_vldb15,
        title = {{Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions}},
        author = {Inoue, Hiroshi and Ohara, Moriyoshi and Taura, Kenjiro},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {3},
        pages = {293--304},
        doi = {10.14778/2735508.2735516},
        url = {https://doi.org/10.14778/2735508.2735516},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024899872
1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.499042e-05
3,881	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.9477894e-05
4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB	6.7180565e-05
7,541	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	5.4977034e-05
8,006	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.4066876e-05
8,372	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	5.3434309e-05
8,385	Interleaved Multi-Vectorizing	2020	VLDB	5.3404356e-05
10,354	Prune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer Set with Morphing Nodes	2027	VLDB	4.9769913e-05
11,893	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022001327
723	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.00014507399
1,653	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.969498e-05
1,730	Improving the Performance of List Intersection	2009	VLDB	9.7686642e-05
2,120	Fast Set Intersection in Memory	2011	VLDB	9.0077549e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,385	Interleaved Multi-Vectorizing	2020	VLDB
2	8,372	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB
3	201	Efficient set joins on similarity predicates	2004	SIGMOD
4	627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD
5	4,225	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
6	723	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
7	1,730	Improving the Performance of List Intersection	2009	VLDB
8	287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD
9	2,120	Fast Set Intersection in Memory	2011	VLDB
10	1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD