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: 13489
Venue: VLDB
Year: 2024
Pagerank: 4.1905499e-05
Overall Rank: 11,041 | 23.27%
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.1905499e-05
10,592	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1905499e-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.00030020929
1,000	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014714977
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
1,256	Influential Community Search in Large Networks	2015	VLDB	0.00013009097
1,653	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.0001098717
1,694	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010870205
1,822	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010404349
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
2,206	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.2958349e-05
2,547	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.5600506e-05
2,643	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3894193e-05
5,035	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	5.7414979e-05
5,059	G-Tran: A High Performance Distributed Graph Database with a Decentralized Architecture	2022	VLDB	5.7207311e-05
5,274	A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery	2022	SIGMOD	5.5919087e-05
5,548	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4445937e-05
5,606	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB	5.4126223e-05
5,933	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2620152e-05
6,796	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9195203e-05
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7236107e-05
7,674	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.677258e-05
8,252	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.544713e-05
9,086	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.3947639e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,843	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010340277
10,592	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	4.1905499e-05
2,643	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.3894193e-05
10,878	A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks	2025	VLDB	4.1905499e-05
9,086	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	4.3947639e-05
9,472	Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks	2025	SIGMOD	4.3300131e-05
1,385	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD	0.00012259478
5,035	Scaling Up Distance Labeling on Graphs with Core-Periphery Properties	2020	SIGMOD	5.7414979e-05
2,206	When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks	2018	SIGMOD	9.2958349e-05
1,822	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.00010404349