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
BibTeX Citation
Copy BibTeX
@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,232
Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding
2024
VLDB
5.84313e-05
6,408
Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks
2023
SIGMOD
5.7942038e-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,555
Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings
2026
SIGMOD
4.9793485e-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,251
Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs
2025
VLDB
4.9793485e-05
11,311
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks
2025
VLDB
4.9793485e-05
11,716
QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks
2023
SIGMOD
4.9793485e-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.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
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
11,311
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks
2025
VLDB
2
11,204
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks
2025
SIGMOD
3
10,576
Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks
2026
SIGMOD
4
1,722
Querying Shortest Paths on Time Dependent Road Networks
2019
VLDB
5
9,799
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks
2025
SIGMOD
6
1,232
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice
2013
SIGMOD
7
5,336
Efficient Shortest Path Counting on Large Road Networks
2022
VLDB
8
1,269
Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions
2011
VLDB
9
1,645
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks
2018
SIGMOD
10
2,141
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees
2020
VLDB