iBFS: Concurrent Breadth-First Search on GPUs

Summary: iBFS is a GPU-based framework for concurrent BFS from multiple sources, with a single joint-traversal kernel, outdegree-based GroupBy to maximize frontier sharing, and bitwise per-vertex checks across BFS instances. Evaluations show up to 30x single-GPU speedup and near-linear scaling to 112 GPUs, achieving peak TEPS in the tens of trillions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5212
Venue: SIGMOD
Year: 2016
Pagerank: 8.0094569e-05
Overall Rank: 2,874 | 80.29%
DOI: 10.1145/2882903.2882959

Incoming Non-self Citations Over Time

Authors

1. Hang Liu (George Washington University)
2. H. Howie Huang (George Washington University)
3. Yang Hu (George Washington University)

BibTeX Citation

@inproceedings{liu_sigmod16,
        title = {{iBFS: Concurrent Breadth-First Search on GPUs}},
        author = {Liu, Hang and Huang, H. Howie and Hu, Yang},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2882959},
        url = {https://dl.acm.org/doi/10.1145/2882903.2882959},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,102	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012166591
4,157	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.8629037e-05
4,171	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.8537202e-05
4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	6.821373e-05
5,250	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.2992176e-05
5,612	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.1501992e-05
7,011	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	5.7263348e-05
7,491	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	5.6059269e-05
9,948	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	5.1915905e-05
10,252	GraphRTX: Lighting the Way to Scalable Graph Analytics	2026	SIGMOD	5.093636e-05
10,435	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.0001080346
2,575	K-Reach: Who is in Your Small World	2012	VLDB	8.3982298e-05
5,507	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.1924452e-05
7,571	Parallel Graph Processing on Graphics Processors Made Easy	2013	VLDB	5.594227e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,112	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD
2	10,205	Bound-Tightened Densest Subgraph Discovery on GPU	2026	SIGMOD
3	10,370	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD
4	2,607	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD
5	5,075	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB
6	2,453	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD
7	2,060	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB
8	4,157	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD
9	5,317	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB
10	1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB