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: hdd1c5e22c607f61b
Venue: SIGMOD
Year: 2018
Pagerank: 9.4720431e-05
Overall Rank: 1,860 | 87.54%
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 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,171	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011677799
1,227	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011426039
1,988	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2301018e-05
2,074	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	9.06339e-05
3,321	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.4117038e-05
5,007	Accelerating Maximal Clique Enumeration via Graph Reduction	2024	VLDB	6.3052426e-05
7,126	GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra	2021	VLDB	5.580601e-05
7,557	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	5.4795245e-05
7,752	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4440674e-05
8,348	Revisiting the Design of In-Memory Dynamic Graph Storage	2025	SIGMOD	5.3337901e-05
9,843	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	5.1064323e-05
9,996	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	5.0845476e-05
10,303	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	5.0294306e-05
10,421	Prune Early, Intersect Fast: PRISM, a Prefix-based Radix Integer Set with Morphing Nodes	2027	VLDB	4.9605343e-05
10,583	Sublime: Selecting Subgraph Matching Algorithms via Machine Learning	2026	SIGMOD	4.9605343e-05
10,613	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.9605343e-05
10,647	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.9605343e-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
182	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026383593
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024929198
218	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024342426
255	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022949287
274	Online Search of Overlapping Communities	2013	SIGMOD	0.00022499515
289	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021955394
485	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017479773
1,440	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010630613
1,658	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.945593e-05
1,720	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7828414e-05
1,737	Improving the Performance of List Intersection	2009	VLDB	9.7383962e-05
2,017	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	9.169662e-05
2,136	Fast Set Intersection in Memory	2011	VLDB	8.9790795e-05
2,988	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.7659651e-05
7,492	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.4981253e-05

Semantically Similar Papers

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