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.9605343e-05
Overall Rank: 11,634 | 22.02%
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

1. Yuanyuan Zeng (Chinese University of Hong Kong)
2. Chenhao Ma (Chinese University of Hong Kong)
3. Yixiang Fang (Chinese University of Hong Kong)

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,757	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	4.9605343e-05
11,315	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.9605343e-05

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
192	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025740385
696	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014671367
931	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00012993132
970	Influential Community Search in Large Networks	2015	VLDB	0.00012749284
1,233	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00011397529
1,346	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00010949128
1,577	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010155939
1,581	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	0.00010151896
1,653	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	9.9588776e-05
2,150	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.9509559e-05
2,201	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8626226e-05
4,214	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	6.7186746e-05
4,617	G-Tran: A High Performance Distributed Graph Database with a Decentralized Architecture	2022	VLDB	6.4848168e-05
4,944	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	6.3297928e-05
5,026	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	6.2965202e-05
5,357	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	6.1514562e-05
5,409	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	6.1320768e-05
5,699	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.0139119e-05
6,192	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.8377174e-05
7,268	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	5.553602e-05
7,399	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	5.5186598e-05
8,416	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3208725e-05

Semantically Similar Papers

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