Partitioned Dynamic Hub Labeling for Large Road Networks

Shortest path computation is ubiquitous in various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, traffic conditions keep changing in real life, making the precomputed index unable to answer the query correctly. In this work, we adopt the state-of-the-art <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">tree decomposition-based hub labeling (TDHL)</i> as the underlying index and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">minimum weight property</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">minimum distance property</i> to guarantee index correctness without graph traversal. Moreover, we propose the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">star-centric paradigm</i> for tracing index change and design various pruning techniques to further accelerate index maintenance. We also extend our algorithms to batch mode for shared computation, to structural maintenance for full types of updates, and generalize to all kinds of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">TDHL</i>. Finally, we further improve the index maintenance efficiency and scalability of our algorithms by leveraging graph partition. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.