DBScholar

Back to papers

Distributed Shortest Distance Labeling on Large-Scale Graphs

Summary: DH-Index: a distributed hop-based distance labeling using a boundary graph that bounds index hops to ≤4 between connected vertices to dramatically cut cross-machine messaging. Hierarchical construction and bidirectional search yield major wins (65.5× indexing, ~1000× queries), with lower memory, communication, and improved scalability. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
h81a8fdd0f499cab7
Venue
VLDB
Year
2024
Pagerank
4.9769913e-05
Overall Rank
11,586 | 22.13%
DOI
10.14778/3675034.3675053
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

BibTeX Citation

@article{zeng_vldb24,
        title = {{Distributed Shortest Distance Labeling on Large-Scale Graphs}},
        author = {Zeng, Yuanyuan and Ma, Chenhao and Fang, Yixiang},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {10},
        pages = {2641--2653},
        doi = {10.14778/3675034.3675053},
        url = {https://doi.org/10.14778/3675034.3675053},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank Citing Paper Year Venue Pagerank
10,696 Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC 2026 SIGMOD 4.9769913e-05
11,259 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank Cited Paper Year Venue Pagerank
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025572265
714 Effective Community Search for Large Attributed Graphs 2016 VLDB 0.00014562182
959 Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs 2014 VLDB 0.00012849025
1,007 Influential Community Search in Large Networks 2015 VLDB 0.00012550629
1,234 Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013 SIGMOD 0.00011404678
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.0001096845
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010158887
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9906562e-05
1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9828268e-05
2,143 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9625587e-05
2,190 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD 8.8832666e-05
4,491 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5750647e-05
4,599 G-Tran: A High Performance Distributed Graph Database with a Decentralized Architecture 2022 VLDB 6.5061447e-05
4,924 A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery 2022 SIGMOD 6.3492725e-05
5,004 Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs 2021 VLDB 6.3172422e-05
5,343 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB 6.1718642e-05
5,705 Hub Labeling for Shortest Path Counting 2020 SIGMOD 6.0274828e-05
5,804 Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement 2022 VLDB 5.9865208e-05
6,180 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 5.8570846e-05
7,250 Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale 2022 VLDB 5.5720266e-05
7,379 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5369684e-05
8,397 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3385249e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB
2 11,259 Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025 VLDB
3 2,190 Scaling Distance Labeling on Small-World Networks 2019 SIGMOD
4 11,455 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB
5 8,397 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD
6 9,806 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD
7 1,253 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD
8 4,491 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD
9 1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD
10 1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB