Back to papers
The More the Merrier: Efficient Multi-Source Graph Traversal
Summary: MS-BFS runs many concurrent BFSs on one graph by sharing work and reducing memory accesses, exploiting small-world properties to avoid synchronization. It achieves near-linear core scalability on real graphs (Twitter, Wikipedia) and outperforms prior BFS for many sources, enabling all-vertices closeness centrality.
(summarized by gpt-5-nano on Feb 09 2026)
- Paper ID
- 11157
- Venue
- VLDB
- Year
- 2015
- Pagerank
- 0.00010967716
- Overall Rank
- 1,665 | 88.42%
- DOI
-
-
Incoming Non-self Citations Over Time
Incoming Citations (Sorted by Pagerank)
Showing 20 of 20 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
| 1,263 |
Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation |
2016 |
SIGMOD |
0.00012982857 |
| 1,484 |
Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks |
2019 |
VLDB |
0.00011714263 |
| 1,676 |
Speedup Graph Processing by Graph Ordering |
2016 |
SIGMOD |
0.00010946423 |
| 3,233 |
iBFS: Concurrent Breadth-First Search on GPUs |
2016 |
SIGMOD |
7.3361904e-05 |
| 3,668 |
The LDBC Social Network Benchmark: Business Intelligence Workload |
2023 |
VLDB |
6.8591612e-05 |
| 5,680 |
Parallel Personalized PageRank on Dynamic Graphs |
2018 |
VLDB |
5.3734643e-05 |
| 6,059 |
Cache-Efficient Fork-Processing Patterns on Large Graphs |
2021 |
SIGMOD |
5.2307519e-05 |
| 7,033 |
DuckPGQ: Bringing SQL/PGQ to DuckDB |
2023 |
VLDB |
4.8551607e-05 |
| 7,255 |
Automatic Algorithm Transformation for Efficient Multi-Snapshot Analytics on Temporal Graphs |
2017 |
VLDB |
4.7877161e-05 |
| 7,589 |
Using Domain-Specific Languages For Analytic Graph Databases |
2016 |
VLDB |
4.7030207e-05 |
| 7,675 |
Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale |
2022 |
VLDB |
4.6817479e-05 |
| 8,669 |
Distributed Set Reachability |
2016 |
SIGMOD |
4.4718257e-05 |
| 9,360 |
MITra: A Framework for Multi-Instance Graph Traversal |
2023 |
VLDB |
4.350809e-05 |
| 9,670 |
On Efficient Large Sparse Matrix Chain Multiplication |
2024 |
SIGMOD |
4.3066148e-05 |
| 9,793 |
uBlade: Efficient Batch Processing for Uncertain Graph Queries |
2024 |
SIGMOD |
4.2818172e-05 |
| 9,952 |
On Scalable Computation of Graph Eccentricities |
2022 |
SIGMOD |
4.2405999e-05 |
| 10,070 |
DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs |
2026 |
SIGMOD |
4.1945683e-05 |
| 10,651 |
Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure |
2025 |
VLDB |
4.1945683e-05 |
| 10,745 |
Robust Recursive Query Parallelism in Graph Database Management Systems |
2025 |
VLDB |
4.1945683e-05 |
| 10,997 |
Automating Vectorized Distributed Graph Computation |
2024 |
SIGMOD |
4.1945683e-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.
Semantically Similar Papers
| Overall Rank |
Paper |
Year |
Venue |
Pagerank |
| 7,308 |
Real Time Discovery of Dense Clusters in Highly Dynamic Graphs: Identifying Real World Events in Highly Dynamic Environments |
2012 |
VLDB |
4.7672834e-05 |
| 3,129 |
Scalable Big Graph Processing in MapReduce |
2014 |
SIGMOD |
7.5008242e-05 |
| 966 |
Streaming Algorithms for k-core Decomposition |
2013 |
VLDB |
0.00014960672 |
| 6,183 |
Efficient Core Maintenance in Large Bipartite Graphs |
2023 |
SIGMOD |
5.1667703e-05 |
| 6,513 |
Efficient Parallel D-core Decomposition at Scale |
2024 |
VLDB |
5.0321577e-05 |
| 4,394 |
When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks |
2017 |
VLDB |
6.224902e-05 |
| 1,472 |
Space Efficient Mining of Multigraph Streams |
2005 |
PODS |
0.00011828662 |
| 10,189 |
Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs |
2026 |
SIGMOD |
4.1945683e-05 |
| 3,233 |
iBFS: Concurrent Breadth-First Search on GPUs |
2016 |
SIGMOD |
7.3361904e-05 |
| 11,064 |
Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks |
2024 |
VLDB |
4.1945683e-05 |