Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks Journal: PACMMOD Volume: 3 1 (SIGMOD) 35 2 DOI: 10.1145/3709685
Muhammad Farhan, Henning Koehler, Qing Wang · 2025
Read Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks Journal: PACMMOD Volume: 3 1 (SIGMOD) 35 2 DOI: 10.1145/3709685 by Muhammad Farhan, Henning Koehler, Qing Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18013.txt.
Introduction
Muhammad Farhan, Henning Koehler, and Qing Wang present, in 2025, a faster way to answer distance questions on road networks that keep changing. Traffic shifts travel times minute by minute, so a stored index must update quickly without slowing each query. Older methods tend to sacrifice one of those two goals, especially on large maps.
Their design pairs two hierarchies with different strengths, one tuned for queries and one for updates, plus a shared labeling. Dynamic algorithms maintain the labels as road weights rise or fall, and a parallel version speeds the work further. Tests on ten large road networks back the design, the authors report.
Catalog record
| CREATOR | Muhammad Farhan, Henning Koehler, Qing Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-18013
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks Journal: PACMMOD Volume: 3 1 (SIGMOD) 35 2 DOI: 10.1145/3709685 Muhammad Farhan, Henning Koehler, Qing Wang Abstract . Computing the shortest-path distance between any two given vertices in road networks is an important problem. A tremendous amount of research has been conducted to address this problem, most of which are limited to static road networks. Since road networks undergo various real-time traffic conditions, there is a pressing need to address this problem for dynamic road networks. Existing state-of-the-art methods incrementally maintain an indexing structure to reflect dynamic changes on road networks. However, these methods suffer from either slow query response time or poor maintenance performance, particularly when road networks are large. In this work, we propose an efficient solution Dual-Hierarchy Labelling (DHL) for distance querying on dynamic road networks from a novel perspective, which incorporates two hierarchies with different but complementary data structures to support efficient query and update processing. Specifically, our proposed solution is comprised of three main components: query hierarchy , update hierarchy , and hierarchical labelling , where query hierarchy enables efficient query answering by exploring only a small subset of vertices in the labels of two query vertices and update hierarchy supports efficient maintenance of distance labelling under edge weight increase or decrease. We further develop dynamic algorithms to reflect dynamic changes by efficiently maintaining the update hierarchy and hierarchical labelling. We also propose a parallel variant of our dynamic algorithms by exploiting labelling structure which aligns well with parallel processing. We evaluate our methods on 10 large road networks and it shows that our methods significantly outperform the state-of-the-art methods, i.e., achieving considerably faster construction and update time, while being consistently 2-4 times faster in terms of query processing and consuming only 10%-20% labelling space. 1. Introduction Typically, a road network is modeled as a dynamic weighted graph G=(V,E,\omega) , where vertices V represent intersections, edges E represent roads between intersections, and \omega assigns weights to edges, such as travel time. In a dynamic road network, it is commonly assumed that vertices and edges remain intact, while the weights of edges may continuously change due to real-time traffic conditions, such as traffic congestion, accidents, or road closures. Given any arbitrary pair (s,t) of vertices, the distance querying problem is to answer the up-to-date shortest-path distance between s and t under these dynamic changes. As a fundamental building block, distance querying plays a crucial role in road applications, such as GPS navigation ( Goldberg and Harrelson 2005 ) , route planning ( Fan and Shi 2010 ) , traffic monitoring ( Kriegel et al. 2007 ) , and POI recommendation ( Yawalkar and Ranu 2019 ) . These applications often demand low-latency responses due to the need of computing thousands to millions of distance queries per second, as part of more complex tasks, which itself needs to be solved frequently. Examples include matching taxi drivers with passengers, optimizing delivery routes with multiple pick up and drop off points that can change dynamically, or providing recommendation on k-nearest POIs to customers. For instance, real-time navigation systems like Google Maps and Waze use preprocessing techniques such as contraction hierarchies ( Geisberger et al. 2008 ) to accelerate the computation of shortest-path distance queries, enabling optimal route suggestions based on current traffic conditions. These conditions are obtained through various sources, such as crowdsourcing (where data like speed and location is collected from users who have the app open on their devices), road sensors, local transportation authorities, and real-time reports from users. This multifaceted approach ensures that traffic data is updated as frequently as possible, often multiple times per minute ( Zheng et al. 2010 ; Ouyang et al. 2020 ) . In a similar vein, companies offering ride-hailing services like Uber and Lyft rely on millions of real-time distance queries to efficiently match drivers with passengers and minimize wait times ( Zhang 2021 ; Huang et al. 2021 ) . To meet user demands, these systems commonly use a hybrid client-server model. Complex real-time computations and traffic updates are handled by the server, while simpler tasks are managed on the client side. This allows for efficient and responsive navigation, even when the internet connection is weak or unavailable. Figure 1 . A high-level comparison of our proposed method DHL with state-of-the-art methods: (a) DCH ( Ouyang et al. 2020 ) and (b) IncH2H ( Zhang and Yu 2022 ) . DCH processes both queries and updates based on CH (i.e., H:=CH ), IncH2H extends DCH to construct another tree hierarchy T to speed up queries, and DHL uses a tree hierarchy as H_{Q} and CH as H_{U} to process queries and updates, separately; L refers to a distance labelling. The grey, green and blue arrows indicate the processes of construction, updating, and querying, respectively. Present work. In this paper, we study the distance querying problem in dynamic road networks, aiming to maintain accurate distance information efficiently while still achieving superior query performance. This task is challenging, as query time and update time are typically considered a trade-off, where improving one often comes at the expense of the other. Previously, several methods ( Geisberger et al. 2012 ; Ouyang et al. 2020 ; Wei et al. 2020 ; Zhang et al. 2021 ; Zhang and Yu 2022 ; Chen et al. 2021 ) have been developed to incrementally maintain precomputed information, ensuring fast and correct responses to distance queries. These methods generally fall into two main categories: (1) Shortcut-based methods ( Geisberger et al. 2012 ; Ouyang et al. 2020 ; Wei et al. 2020 ) , which focus on maintaining precomputed auxiliary edges, referred to as shortcuts , between vertices by applying vertex contraction in terms of a given vertex ordering, e.g., contraction hierarchy (CH) ( Geisberger et al. 2008 ) . Such shortcuts help reduce query search space. (2) Hub-based labelling methods ( Zhang et al. 2021 ; Zhang and Yu 2022 ; Chen et al. 2021 ) , which maintain distance labelling in addition to shortcuts so that distance queries can be answered by searching distance labels directly. However, these methods require constructing an additional tree decomposition based on CH. In a nutshell, shortcut-based methods require less space and shorter update time, but query time can be orders of magnitude longer than hub-based labelling methods. In contrast, hub-based labelling methods answer distance queries significantly faster at the cost of requiring additional space for storing distance labels and longer update time due to the combined maintenance of distance labels and shortcuts. The table in Figure 1 presents the empirical results on two large real-world road networks: one from USA ( Demetrescu et al. 2009 ) and the other from Europe ( AG [n. d.] ) . To tackle the challenge of efficiently maintaining accurate distance information without compromising query performance, we make two crucial observations: • Separation of concerns : Queries and updates are distinct types of operations. Therefore, different data structures can be employed to efficiently support distance queries and updates separately. • Vertex ordering : Finding a vertex ordering based on the centrality of vertices in a road network plays a vital role in accelerating the