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.9605343e-05
Overall Rank
11,507 | 22.87%
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.0012089097
22 Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud 2012 VLDB 0.00056028465
192 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025740385
376 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019655871
1,346 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010949128
1,581 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 0.00010151896
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
2,794 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.987154e-05
3,935 Effective Caching of Shortest Paths for Location-Based Services 2012 SIGMOD 6.8990945e-05
4,214 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.7186746e-05
5,308 Parallel Personalized PageRank on Dynamic Graphs 2018 VLDB 6.1739397e-05
5,743 Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints 2021 SIGMOD 5.9933367e-05
5,899 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.9376618e-05
6,073 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.8780393e-05
7,008 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6061911e-05
7,323 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5392408e-05
7,399 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5186598e-05
7,736 Accelerating Exact Constrained Shortest Paths on GPUs 2021 VLDB 5.4477033e-05
8,416 Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs 2024 SIGMOD 5.3208725e-05
9,200 Planting Trees for scalable and efficient Canonical Hub Labeling 2020 VLDB 5.1951474e-05
9,578 FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints 2022 VLDB 5.1419143e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 10,719 High-Throughput k Nearest Neighbors Search in Road Networks 2026 SIGMOD
2 11,271 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD
3 1,250 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,634 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB
6 7,399 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB
7 5,899 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD
8 2,794 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD
9 8,695 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD
10 1,581 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD