Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks
Authors:
- Zi ChenZCZi Chen
- Bo FengBFBo Feng
- Long YuanLYLong Yuan
- Xuemin LinXLXuemin Lin
- Liping WangLWLiping Wang
Open Access
- 4 September 2023
- journal article
- research article
- Published by Springer Nature in Data Science and Engineering
- Vol. 8 (3) , 263-278
Abstract
In the real world, road networks with weight and label on edges can be applied in several application domains. The shortest path query with label restrictions has been receiving increasing attention recently. To efficiently answer such kind of queries, a novel index, namely Contraction Hierarchies with Label Restrictions (CHLR), is proposed in the literature. However, existing studies mainly focus on the static road networks and do not support the CHLR maintenance when the road networks are dynamically changed. Motivated by this, in this paper, we investigate the CHLR maintenance problem in dynamic road networks. We first devise a baseline approach to update CHLR by recomputing the potential affected shortcuts. However, many shortcuts recomputed in baseline do not change in fact, which leads to unnecessary overhead of the baseline. To overcome the drawbacks of baseline, we further propose a novel CHLR maintenance algorithm which can only travel little shortcuts through an update propagate chain with accuracy guarantee. Moreover, an optimization strategy is presented to further improve the efficiency of index maintenance. Considering the frequency of edge changes, we also propose a batch index maintenance algorithm to handle batch edge changes which can process a large number of edge changes at once. Furthermore, a parallel method is proposed to further accelerate calculations. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the efficiency and effectiveness of our proposed algorithms.Keywords
This publication has 29 references indexed in Scilit:
- Index-Based Densest Clique Percolation Community Search in NetworksIEEE Transactions on Knowledge and Data Engineering, 2017
- Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs2016
- Efficient single-source shortest path and distance queries on large graphs2013
- Shortest path and distance queries on road networks2013
- Fast exact shortest-path distance queries on large networks by pruned landmark labeling2013
- Shortest path and distance queries on road networksProceedings of the VLDB Endowment, 2012
- A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks2011
- Graph indexing of road networks for shortest path queries with label restrictionsProceedings of the VLDB Endowment, 2010
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks2008
- A note on two problems in connexion with graphsNumerische Mathematik, 1959