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: 13488
Venue: VLDB
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 11,038 | 23.22%
DOI: 10.14778/3675034.3675053

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,209	Scalable Privacy-Preserving Shortest Path Distance Computation via 2-Hop Labeling in MPC	2026	SIGMOD	4.1945683e-05
10,584	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1945683e-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
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
999	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014726563
1,171	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013511313
1,257	Influential Community Search in Large Networks	2015	VLDB	0.00013020648
1,654	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.000109978
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
2,201	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.3048105e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5683079e-05
2,639	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3975113e-05
5,035	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	5.7470184e-05
5,064	G-Tran: A High Performance Distributed Graph Database with a Decentralized Architecture	2022	VLDB	5.7261007e-05
5,265	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	5.5972878e-05
5,540	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4498271e-05
5,597	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4178241e-05
5,932	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2670741e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
7,675	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.6817479e-05
8,256	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.5490743e-05
9,089	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.39898e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881
10,584	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1945683e-05
2,639	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3975113e-05
10,874	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.1945683e-05
9,089	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.39898e-05
9,470	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD	4.3341665e-05
1,378	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012294512
5,035	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	5.7470184e-05
2,201	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.3048105e-05
1,823	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010413508