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.0882436e-05
Overall Rank
3,676 | 75.37%
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
5,899
Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023
SIGMOD
5.9376618e-05
6,245
Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024
VLDB
5.8210521e-05
8,695
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025
SIGMOD
5.2717835e-05
10,044
PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks 2024
VLDB
5.0786422e-05
10,630
Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings 2026
SIGMOD
4.9605343e-05
10,638
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach 2026
SIGMOD
4.9605343e-05
11,271
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025
SIGMOD
4.9605343e-05
11,272
Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks 2025
SIGMOD
4.9605343e-05
11,315
Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs 2025
VLDB
4.9605343e-05
11,373
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025
VLDB
4.9605343e-05
11,768
QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks 2023
SIGMOD
4.9605343e-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.0010688884
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
449
Scalable Network Distance Browsing in Spatial Databases 2008
SIGMOD
0.00018112854
954
Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012
VLDB
0.00012856563
993
Path Oracles for Spatial Networks 2009
VLDB
0.00012620373
1,233
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013
SIGMOD
0.00011397529
1,250
A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012
SIGMOD
0.00011325987
1,323
Incremental Graph Pattern Matching 2011
SIGMOD
0.00011019578
1,346
An Experimental Study on Hub Labeling based Shortest Path Algorithms 2018
VLDB
0.00010949128
1,577
Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014
VLDB
0.00010155939
1,581
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018
SIGMOD
0.00010151896
1,653
IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013
VLDB
9.9588776e-05
2,150
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020
VLDB
8.9509559e-05
2,794
P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021
SIGMOD
7.987154e-05
2,854
Incremental Graph Computations: Doable and Undoable 2017
SIGMOD
7.9179612e-05
3,933
Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012
SIGMOD
6.9003202e-05
4,557
Incrementalizing Graph Algorithms 2021
SIGMOD
6.5264915e-05
4,631
Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks 2020
SIGMOD
6.4784075e-05
5,938
Incrementalization of Graph Partitioning Algorithms 2020
VLDB
5.9223788e-05
6,073
Progressive Top-K Nearest Neighbors Search in Large Road Networks 2020
SIGMOD
5.8780393e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
11,373
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks 2025
VLDB
2
11,271
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks 2025
SIGMOD
3
9,679
Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks 2026
SIGMOD
4
1,717
Querying Shortest Paths on Time Dependent Road Networks 2019
VLDB
5
8,695
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025
SIGMOD
6
1,233
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice 2013
SIGMOD
7
5,357
Efficient Shortest Path Counting on Large Road Networks 2022
VLDB
8
1,270
Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions 2011
VLDB
9
1,581
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018
SIGMOD
10
2,150
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020
VLDB