DBScholar

Back to papers

Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees

Summary: Maintains Contraction Hierarchies under streaming and batch road-network updates via a shortcut-centric SS-Graph and weight propagation, avoiding broad index reconstruction. Provides theoretical guarantees and 2–3 orders-of-magnitude faster streaming maintenance than prior work. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
ha9414779f82483ee
Venue
VLDB
Year
2020
Pagerank
8.9625587e-05
Overall Rank
2,143 | 85.60%
DOI
10.14778/3377369.3377371
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{ouyang_vldb20,
        title = {{Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees}},
        author = {Ouyang, Dian and Yuan, Long and Qin, Lu and Chang, Lijun and Zhang, Ying and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {5},
        pages = {602--615},
        doi = {10.14778/3377369.3377371},
        url = {https://doi.org/10.14778/3377369.3377371},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
2,944 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8277412e-05
3,689 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0921741e-05
6,991 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6247902e-05
7,250 Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale 2022 VLDB 5.5720266e-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
8,701 QARTA: An ML-based System for Accurate Map Services 2021 VLDB 5.2880532e-05
9,416 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.180378e-05
9,806 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.1233734e-05
10,009 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.0954911e-05
10,575 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 4.9769913e-05
11,213 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9769913e-05
11,214 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.9769913e-05
11,271 Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints 2025 VLDB 4.9769913e-05
11,319 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.9769913e-05
11,455 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.9769913e-05
11,586 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9769913e-05
11,770 Automatic Road Extraction with Multi-Source Data Revisited: Completeness, Smoothness and Discrimination 2023 VLDB 4.9769913e-05
12,020 A Demonstration of QARTA: An ML-based System for Accurate Map Services 2021 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers