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.0921741e-05
Overall Rank
3,689 | 75.21%
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,235
Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding
2024
VLDB
5.8403639e-05
6,411
Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks
2023
SIGMOD
5.7914609e-05
9,806
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks
2025
SIGMOD
5.1233734e-05
10,009
PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks
2024
VLDB
5.0954911e-05
10,566
Continuous Subgraph Matching via Cost-Model-based Dynamic Vertex Dominance Embeddings
2026
SIGMOD
4.9769913e-05
10,575
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
2026
SIGMOD
4.9769913e-05
11,213
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks
2025
SIGMOD
4.9769913e-05
11,214
Efficient Indexing for Flexible Label-Constrained Shortest Path Queries in Road Networks
2025
SIGMOD
4.9769913e-05
11,259
Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs
2025
VLDB
4.9769913e-05
11,319
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks
2025
VLDB
4.9769913e-05
11,722
QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks
2023
SIGMOD
4.9769913e-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.0010679903
197
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
2013
SIGMOD
0.00025572265
382
TEDI: Efficient Shortest Path Query Answering on Graphs
2010
SIGMOD
0.00019477423
447
Scalable Network Distance Browsing in Spatial Databases
2008
SIGMOD
0.00018151383
953
Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation
2012
VLDB
0.00012871412
991
Path Oracles for Spatial Networks
2009
VLDB
0.00012642908
1,234
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice
2013
SIGMOD
0.00011404678
1,253
A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs
2012
SIGMOD
0.00011331798
1,318
Incremental Graph Pattern Matching
2011
SIGMOD
0.00011044781
1,340
An Experimental Study on Hub Labeling based Shortest Path Algorithms
2018
VLDB
0.0001096845
1,585
Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks
2014
VLDB
0.00010158887
1,645
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks
2018
SIGMOD
9.9906562e-05
1,647
IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying
2013
VLDB
9.9828268e-05
2,143
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees
2020
VLDB
8.9625587e-05
2,851
Incremental Graph Computations: Doable and Undoable
2017
SIGMOD
7.9382307e-05
2,944
P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators
2021
SIGMOD
7.8277412e-05
3,936
Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach
2012
SIGMOD
6.9140006e-05
4,541
Incrementalizing Graph Algorithms
2021
SIGMOD
6.547718e-05
4,636
Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks
2020
SIGMOD
6.4902578e-05
5,926
Incrementalization of Graph Partitioning Algorithms
2020
VLDB
5.9415738e-05
6,087
Progressive Top-K Nearest Neighbors Search in Large Road Networks
2020
SIGMOD
5.8890302e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
11,319
Customization Meets 2-Hop Labeling: Efficient Routing in Road Networks
2025
VLDB
2
11,213
Divide-and-Conquer: Scalable Shortest Path Counting on Large Road Networks
2025
SIGMOD
3
10,587
Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks
2026
SIGMOD
4
1,724
Querying Shortest Paths on Time Dependent Road Networks
2019
VLDB
5
9,806
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks
2025
SIGMOD
6
1,234
Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice
2013
SIGMOD
7
5,343
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,645
When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks
2018
SIGMOD
10
2,143
Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees
2020
VLDB