Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions

Summary: Presents QFilter, a SIMD-accelerated set-intersection for graph adjacency lists using a merge-based scheme with one-byte pruning. With BSR, a compact binary set representation, it achieves two-level data parallelism; node ordering is NP-hard, tackled by a practical approximate algorithm and experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5632
Venue: SIGMOD
Year: 2018
Pagerank: 9.1514258e-05
Overall Rank: 2,112 | 85.52%
DOI: 10.1145/3183713.3196924

Incoming Non-self Citations Over Time

Authors

1. Shuo Han (Peking University)
2. Lei Zou (Peking University)
3. Jeffery Xu Yu (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{han_sigmod18,
        title = {{Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions}},
        author = {Han, Shuo and Zou, Lei and Yu, Jeffery Xu},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196924},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196924},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,211	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011648789
1,237	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011545768
2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2787188e-05
2,060	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	9.2454783e-05
3,686	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.2029305e-05
6,961	GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra	2021	VLDB	5.7303405e-05
7,444	Accelerating Maximal Clique Enumeration via Graph Reduction	2024	VLDB	5.6166432e-05
7,624	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.5805027e-05
8,154	Revisiting the Design of In-Memory Dynamic Graph Storage	2025	SIGMOD	5.4769071e-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,624	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	5.2434488e-05
10,294	Sublime: Selecting Subgraph Matching Algorithms via Machine Learning	2026	SIGMOD	5.093636e-05
10,332	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	5.093636e-05
10,375	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	5.093636e-05
10,376	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	5.093636e-05
11,087	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
189	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026114928
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
216	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024498128
262	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00023084332
273	Online Search of Overlapping Communities	2013	SIGMOD	0.00022671795
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017717377
1,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010538011
1,655	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	0.00010103504
1,717	Improving the Performance of List Intersection	2009	VLDB	9.9327227e-05
1,761	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.8154969e-05
2,224	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.9183396e-05
2,245	Fast Set Intersection in Memory	2011	VLDB	8.8734284e-05
3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.6328776e-05
7,242	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.6641994e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,375	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD
2	8,437	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS
3	6,855	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS
4	10,558	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB
5	1,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD
6	4,157	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD
7	2,245	Fast Set Intersection in Memory	2011	VLDB
8	1,717	Improving the Performance of List Intersection	2009	VLDB
9	9,176	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD
10	3,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB