DBScholar

Back to papers

Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks

Summary: Analyzes incremental CH and H2H for dynamic road networks. Proposes relative subboundedness as an alternative to boundedness, and delivers relatively subbounded CH/H2H algorithms with real-network tests beating full recomputation at 10% updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hf5e7274fa0e47d1e
Venue
SIGMOD
Year
2022
Pagerank
7.0955331e-05
Overall Rank
3,687 | 75.22%
DOI
10.1145/3514221.3517875

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{zhang_sigmod22,
        title = {{Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks}},
        author = {Zhang, Yikai and Yu, Jeffrey Xu},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517875},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517875},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 21 of 21 cited papers.

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

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679641
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025584127
382 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019485934
447 Scalable Network Distance Browsing in Spatial Databases 2008 SIGMOD 0.00018159715
953 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB 0.00012877507
990 Path Oracles for Spatial Networks 2009 VLDB 0.00012648672
1,232 Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013 SIGMOD 0.0001141008
1,252 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD 0.00011336944
1,317 Incremental Graph Pattern Matching 2011 SIGMOD 0.00011050011
1,340 An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018 VLDB 0.00010973645
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010163696
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9953879e-05
1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9875545e-05
2,141 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9668034e-05
2,851 Incremental Graph Computations: Doable and Undoable 2017 SIGMOD 7.9419904e-05
2,943 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8314485e-05
3,934 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD 6.9172713e-05
4,540 Incrementalizing Graph Algorithms 2021 SIGMOD 6.5508191e-05
4,633 Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020 SIGMOD 6.4933316e-05
5,926 Incrementalization of Graph Partitioning Algorithms 2020 VLDB 5.9443878e-05
6,107 Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020 SIGMOD 5.8852347e-05
Previous Page 1 / 1 Next

Semantically Similar Papers