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.1750421e-05
Overall Rank: 2,019 | 86.43%
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,180	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00011627669
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
2,014	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.1832045e-05
2,068	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	9.0920811e-05
3,314	Accelerating Triangle Counting on GPU	2021	SIGMOD	7.4380767e-05
4,981	Accelerating Maximal Clique Enumeration via Graph Reduction	2024	VLDB	6.329157e-05
7,101	GraphMineSuite: Enabling High-Performance and Programmable Graph Mining Algorithms with Set Algebra	2021	VLDB	5.601767e-05
7,747	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4601389e-05
8,327	Revisiting the Design of In-Memory Dynamic Graph Storage	2025	SIGMOD	5.35402e-05
9,351	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD	5.1890979e-05
9,802	RapidStore: An Efficient Dynamic Graph Storage System for Concurrent Queries	2025	VLDB	5.1257999e-05
9,957	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	5.1038322e-05
10,270	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	5.0485061e-05
10,506	Sublime: Selecting Subgraph Matching Algorithms via Machine Learning	2026	SIGMOD	4.9793485e-05
10,537	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.9793485e-05
10,573	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.9793485e-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
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026100147
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
219	SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units	2009	VLDB	0.00024363532
265	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022748633
284	Online Search of Overlapping Communities	2013	SIGMOD	0.00022208562
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021970198
490	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017438618
1,440	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010641888
1,671	Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units	2011	VLDB	9.9310625e-05
1,723	ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout	2015	SIGMOD	9.7931223e-05
1,769	Improving the Performance of List Intersection	2009	VLDB	9.6869284e-05
2,201	An Experimental Study of Bitmap Compression vs. Inverted List Compression	2017	SIGMOD	8.8726671e-05
2,316	Fast Set Intersection in Memory	2011	VLDB	8.6496494e-05
3,289	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.4528818e-05
7,495	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.5091753e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,270	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD
2	8,599	A Generic Flow Algorithm for Shared Filter Ordering Problems	2008	PODS
3	6,957	2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection	2017	PODS
4	10,740	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,207	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD
7	2,316	Fast Set Intersection in Memory	2011	VLDB
8	1,769	Improving the Performance of List Intersection	2009	VLDB
9	9,351	HERO: A Hierarchical Set Partitioning and Join Framework for Speeding up the Set Intersection Over Graphs	2024	SIGMOD
10	3,289	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB