DBScholar

Back to papers

A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks

Summary: G2H is a CPU-GPU hybrid hop-labeling method for rapidly rebuilding road-network distance indexes under frequent updates, combining hybrid graph partitioning, optimized ordering, and parallel label pruning. It constructs indexes for 6M-vertex networks in under a minute and serves hundreds of millions of queries per second. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h8e9a15bb0d33fb80
Venue
VLDB
Year
2025
Pagerank
4.9769913e-05
Overall Rank
11,455 | 23.01%
DOI
10.14778/3712221.3712241
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{li_vldb25,
        title = {{A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks}},
        author = {Li, Jiajia and Chen, Yongzhi and Zhang, Mengxuan and Li, Lei},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {3},
        pages = {770--783},
        doi = {10.14778/3712221.3712241},
        url = {https://doi.org/10.14778/3712221.3712241},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
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
3 Pregel: A System for Large-Scale Graph Processing 2010 SIGMOD 0.0012087459
22 Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud 2012 VLDB 0.00055938421
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025572265
382 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019477423
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.0001096845
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9906562e-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
2,944 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8277412e-05
3,921 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 6.9219828e-05
4,491 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5750647e-05
5,303 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 6.1867551e-05
5,731 Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints 2021 SIGMOD 6.0126206e-05
6,087 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.8890302e-05
6,411 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7914609e-05
6,991 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6247902e-05
7,305 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5576178e-05
7,379 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5369684e-05
7,723 Accelerating Exact Constrained Shortest Paths on GPUs 2021 VLDB 5.4657765e-05
8,397 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3385249e-05
9,175 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.2123828e-05
9,553 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1589731e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,658 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD
2 11,213 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD
3 1,253 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD
4 1,270 Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011 VLDB
5 11,586 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB
6 7,379 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB
7 6,411 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD
8 2,944 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD
9 9,806 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD
10 1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD