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
6389
Venue
SIGMOD
Year
2022
Pagerank
7.2579119e-05
Overall Rank
3,612 | 75.22%
DOI
10.1145/3514221.3517875
Incoming Non-self Citations Over Time
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.
Rank
Citing Paper
Year
Venue
Pagerank
6,149
Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024
VLDB
5.9581422e-05
6,292
Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023
SIGMOD
5.9251728e-05
9,619
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025
SIGMOD
5.2434488e-05
9,815
PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024
VLDB
5.214913e-05
10,354
Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026
SIGMOD
5.093636e-05
10,366
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026
SIGMOD
5.093636e-05
10,788
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025
SIGMOD
5.093636e-05
10,789
Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025
SIGMOD
5.093636e-05
10,845
Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025
VLDB
5.093636e-05
10,918
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025
VLDB
5.093636e-05
11,401
QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023
SIGMOD
5.093636e-05
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.0010828372
195
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013
SIGMOD
0.00025813775
370
TEDI: Efficient Shortest Path Query Answering on Graphs 2010
SIGMOD
0.00019937972
433
Scalable Network Distance Browsing in Spatial Databases 2008
SIGMOD
0.00018532516
949
Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012
VLDB
0.00013028107
968
Path Oracles for Spatial Networks 2009
VLDB
0.00012901559
1,205
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013
SIGMOD
0.00011664469
1,232
A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012
SIGMOD
0.00011566372
1,296
Incremental Graph Pattern Matching 2011
SIGMOD
0.00011269684
1,309
An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018
VLDB
0.00011210911
1,553
Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014
VLDB
0.0001037809
1,613
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018
SIGMOD
0.00010216983
1,622
IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013
VLDB
0.00010201102
2,097
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020
VLDB
9.1725037e-05
2,798
Incremental Graph Computations: Doable and Undoable 2017
SIGMOD
8.1129891e-05
2,871
P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021
SIGMOD
8.0110616e-05
3,857
Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012
SIGMOD
7.0678455e-05
4,443
Incrementalizing Graph Algorithms 2021
SIGMOD
6.7004839e-05
4,786
Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020
SIGMOD
6.5083151e-05
5,811
Incrementalization of Graph Partitioning Algorithms 2020
VLDB
6.0782651e-05
5,987
Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020
SIGMOD
6.0183678e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
10,918
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025
VLDB
2
10,788
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025
SIGMOD
3
10,379
Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026
SIGMOD
4
1,745
Querying Shortest Paths on Time Dependent Road Networks 2019
VLDB
5
9,619
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025
SIGMOD
6
1,205
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013
SIGMOD
7
5,208
Efficient Shortest Path Counting on Large Road Networks 2022
VLDB
8
1,251
Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011
VLDB
9
1,613
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018
SIGMOD
10
2,097
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020
VLDB