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: 11158
Venue: VLDB
Year: 2015
Pagerank: 0.00010958779
Overall Rank: 1,665 | 88.43%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,260	Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation	2016	SIGMOD	0.00012990853
1,484	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011705344
1,670	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010944596
3,235	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	7.3298263e-05
3,670	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	6.8557811e-05
5,693	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	5.3683002e-05
5,966	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	5.2471834e-05
7,021	DuckPGQ: Bringing SQL/PGQ to DuckDB	2023	VLDB	4.8546368e-05
7,252	Automatic Algorithm Transformation for Efficient Multi-Snapshot Analytics on Temporal Graphs	2017	VLDB	4.7832161e-05
7,592	Using Domain-Specific Languages For Analytic Graph Databases	2016	VLDB	4.6985656e-05
7,674	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.677258e-05
8,667	Distributed Set Reachability	2016	SIGMOD	4.467539e-05
9,367	MITra: A Framework for Multi-Instance Graph Traversal	2023	VLDB	4.3466395e-05
9,670	On Efficient Large Sparse Matrix Chain Multiplication	2024	SIGMOD	4.3024878e-05
9,796	uBlade: Efficient Batch Processing for Uncertain Graph Queries	2024	SIGMOD	4.2777144e-05
9,951	On Scalable Computation of Graph Eccentricities	2022	SIGMOD	4.236537e-05
10,070	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.1905499e-05
10,659	Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure	2025	VLDB	4.1905499e-05
10,752	Robust Recursive Query Parallelism in Graph Database Management Systems	2025	VLDB	4.1905499e-05
11,000	Automating Vectorized Distributed Graph Computation	2024	SIGMOD	4.1905499e-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
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
39	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00075263552
558	Trinity: A Distributed Graph Engine on a Memory Cloud	2013	SIGMOD	0.00020158056
2,486	Large-Scale Graph Analytics in Aster 6: Bringing Context to Big Data Discovery	2014	VLDB	8.6644935e-05
2,762	K-Reach: Who is in Your Small World	2012	VLDB	8.1614818e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014947141
6,185	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD	5.1618114e-05
6,509	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0273291e-05
4,391	When Engagement Meets Similarity: Efficient (k,r)-Core Computation on Social Networks	2017	VLDB	6.2190075e-05
1,466	Space Efficient Mining of Multigraph Streams	2005	PODS	0.00011838607
10,189	Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs	2026	SIGMOD	4.1905499e-05
3,235	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	7.3298263e-05
11,067	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	4.1905499e-05