A Robust and Globally-Accurate Hierarchical Hub Labeling Index for SP-Distance Queries in Dynamic Road Networks

Computing shortest-path distances between two points in road networks, typically modeled as dynamic weighted graphs due to fluctuating travel times, is fundamental to many location-based services demanding both accuracy and low latency. Existing hierarchical distance indexes for such graphs often face a trade-off: some rely on unstable hierarchies that increase update costs, while others use locally accurate labels that compromise query efficiency. To address this issue, we propose RAHL (Robust and globally-Accurate hierarchical Hub Labeling) index, built via recursive graph partitioning using hub (cut) vertex sets. RAHL ensures stable, invariant hub sets that maintain the global cut property and stores globally accurate distance labels for all vertices. This allows shortest-path queries to be answered simply via lowest-common-ancestor hub lookups. Since hub sets remain stable as edge weights change, updates involve only incremental adjustments to a small set of affected labels, significantly reducing maintenance overhead. Empirical evaluation on real road networks shows that RAHL delivers SOTA query performance while matching or improving index-maintenance efficiency compared with leading baselines, providing a practical balance of low-latency queries and low update cost for large, dynamic networks.