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: h096884743d5da1fe
Venue: SIGMOD
Year: 2016
Pagerank: 8.0116036e-05
Overall Rank: 2,789 | 81.25%
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 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012013426
3,653	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	7.1288161e-05
4,207	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.7343908e-05
4,237	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.7107028e-05
5,300	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.1896851e-05
5,734	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.0137932e-05
6,249	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	5.8358127e-05
6,509	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	5.7601316e-05
10,132	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	5.0751052e-05
10,465	GraphRTX: Lighting the Way to Scalable Graph Analytics	2026	SIGMOD	4.9793485e-05
10,624	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	4.9793485e-05
10,871	Efficient GPU-Accelerated Adaptive Minimum Cost Seed Selection	2026	VLDB	4.9793485e-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
274	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022490994
693	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00014734389
1,442	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010639351
2,604	K-Reach: Who is in Your Small World	2012	VLDB	8.2302549e-05
5,581	Neighborhood-Privacy Protected Shortest Distance Computing in Cloud	2011	SIGMOD	6.076839e-05
7,630	Parallel Graph Processing on Graphics Processors Made Easy	2013	VLDB	5.4800737e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,421	Bound-Tightened Densest Subgraph Discovery on GPU	2026	SIGMOD
2	10,568	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD
3	2,468	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD
4	2,320	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD
5	5,172	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB
6	2,068	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB
7	10,882	Efficient GPU-Accelerated Local Subgraph Counting	2026	VLDB
8	4,207	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD
9	5,139	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB
10	1,442	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB