DBScholar

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
h2a916ba63234522c
Venue
VLDB
Year
2015
Pagerank
0.00010606126
Overall Rank
1,446 | 90.31%
DOI
10.14778/2735496.2735507
PDF
Download (CC BY-NC-ND 3.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{then_vldb15,
        title = {{The More the Merrier: Efficient Multi-Source Graph Traversal}},
        author = {Then, Manuel and Pham, Kien and Kaufmann, Moritz and Kemper, Alfons and Chirigati, Fernando and Hoang-Vu, Tuan-Anh and Neumann, Thomas and Vo, Huy T.},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {4},
        pages = {449},
        doi = {10.14778/2735496.2735507},
        url = {https://doi.org/10.14778/2735496.2735507},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank Citing Paper Year Venue Pagerank
894 Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation 2016 SIGMOD 0.00013179915
1,227 Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks 2019 VLDB 0.00011426039
1,440 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010630613
2,797 iBFS: Concurrent Breadth-First Search on GPUs 2016 SIGMOD 7.9831781e-05
3,066 The LDBC Social Network Benchmark: Business Intelligence Workload 2023 VLDB 7.6714389e-05
5,265 DuckPGQ: Bringing SQL/PGQ to DuckDB 2023 VLDB 6.1922502e-05
5,308 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 6.1739397e-05
5,735 Cache-Efficient Fork-Processing Patterns on Large Graphs 2021 SIGMOD 5.9957538e-05
7,177 Automatic Algorithm Transformation for Efficient Multi-Snapshot Analytics on Temporal Graphs 2017 VLDB 5.5772803e-05
7,268 Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale 2022 VLDB 5.553602e-05
7,778 Using Domain-Specific Languages For Analytic Graph Databases 2016 VLDB 5.4379421e-05
8,097 Robust Recursive Query Parallelism in Graph Database Management Systems 2025 VLDB 5.3739121e-05
8,816 Distributed Set Reachability 2016 SIGMOD 5.2567916e-05
9,192 Automating Vectorized Distributed Graph Computation 2024 SIGMOD 5.1967502e-05
9,649 MITra: A Framework for Multi-Instance Graph Traversal 2023 VLDB 5.1324359e-05
9,985 On Efficient Large Sparse Matrix Chain Multiplication 2024 SIGMOD 5.0849662e-05
10,173 uBlade: Efficient Batch Processing for Uncertain Graph Queries 2024 SIGMOD 5.0559291e-05
10,361 On Scalable Computation of Graph Eccentricities 2022 SIGMOD 5.014328e-05
10,635 DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026 SIGMOD 4.9605343e-05
11,362 Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure 2025 VLDB 4.9605343e-05
Previous Page 1 / 1 Next

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.

Previous Page 1 / 1 Next

Semantically Similar Papers