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.9668034e-05
Overall Rank
2,141 | 85.61%
DOI
10.14778/3377369.3377371

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,943 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8314485e-05
3,687 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0955331e-05
6,988 An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network 2021 VLDB 5.6274541e-05
7,248 Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale 2022 VLDB 5.5746656e-05
7,302 BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale 2022 SIGMOD 5.5602499e-05
7,377 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB 5.5395908e-05
8,693 QARTA: An ML-based System for Accurate Map Services 2021 VLDB 5.2905577e-05
9,407 Continuously Monitoring Alternative Shortest Paths on Road Networks 2020 VLDB 5.1828314e-05
9,799 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.1257999e-05
10,004 PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024 VLDB 5.0979044e-05
10,564 Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026 SIGMOD 4.9793485e-05
11,204 Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025 SIGMOD 4.9793485e-05
11,205 Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025 SIGMOD 4.9793485e-05
11,263 Continuous Lifelong Conflict-Aware AGV Routing with Kinematic Constraints 2025 VLDB 4.9793485e-05
11,311 Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025 VLDB 4.9793485e-05
11,449 A CPU-GPU Hybrid Labelling Algorithm for Massive Shortest Distance Queries on Road Networks 2025 VLDB 4.9793485e-05
11,580 Distributed Shortest Distance Labeling on Large-Scale Graphs 2024 VLDB 4.9793485e-05
11,764 Automatic Road Extraction with Multi-Source Data Revisited: Completeness, Smoothness and Discrimination 2023 VLDB 4.9793485e-05
12,014 A Demonstration of QARTA: An ML-based System for Accurate Map Services 2021 VLDB 4.9793485e-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