Parallel Contraction Hierarchies Can Be Efficient and Scalable Conference: 2025 International Conference on Supercomputing; June 8–11, 2025; Salt Lake City, UT, USA 2025 International Conference on Supercomputing (ICS ’25), June 8–11, 2025, Salt Lake City, UT, USA DOI: 10.1145/3721145.3725744 ISBN:

Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, Yihan Sun · 2024

Read Parallel Contraction Hierarchies Can Be Efficient and Scalable Conference: 2025 International Conference on Supercomputing; June 8–11, 2025; Salt Lake City, UT, USA 2025 International Conference on Supercomputing (ICS ’25), June 8–11, 2025, Salt Lake City, UT, USA DOI: 10.1145/3721145.3725744 ISBN: by Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, Yihan Sun (2024) 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-2412-18008.txt.

Introduction

Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, and Yihan Sun speed up, in a 2024 preprint, the preprocessing behind the fastest road-network route finders. Contraction hierarchies rank road junctions and add shortcut edges, so later route queries run orders of magnitude faster than classic search. Building that hierarchy is slow, and earlier parallel builders barely beat one-core versions. The authors redesign the construction for parallel machines. Their system, SPoCH, reworks both the algorithm and its data structures.

Across sixteen graphs of varied kinds, SPoCH built hierarchies far faster than the best rivals. Speedups ran from eleven to sixty-eight times over the top sequential code. Against the best parallel code, gains ran from about four to forty-one times. Query speed and hierarchy size stayed competitive. Code and datasets are released. The authors aim at map services that must rebuild road data often.

Catalog record

CREATORZijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, Yihan Sun
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-18008

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Contraction Hierarchies Can Be Efficient and Scalable Conference: 2025 International Conference on Supercomputing; June 8–11, 2025; Salt Lake City, UT, USA 2025 International Conference on Supercomputing (ICS ’25), June 8–11, 2025, Salt Lake City, UT, USA DOI: 10.1145/3721145.3725744 ISBN: 979-8-4007-1537-2/2025/06 CCS: Theory of computation Graph algorithms analysis CCS: Theory of computation Shortest paths CCS: Theory of computation Parallel algorithms CCS: Theory of computation Shared memory algorithms Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, Yihan Sun Abstract . Contraction Hierarchies (CH) (Geisberger et al., 2008) is one of the most widely used algorithms for shortest-path queries on road networks. Compared to Dijkstra’s algorithm, CH enables orders of magnitude faster query performance through a preprocessing phase, which iteratively categorizes vertices into hierarchies and adds shortcuts. However, constructing a CH is an expensive task. Existing solutions, including parallel ones, may suffer from long construction time. Especially, in our experiments, we observe that existing parallel solutions demonstrate unsatisfactory scalability, and have performance close to sequential algorithms. We present SPoCH ( S calable P arallelization o f C ontraction H ierarchies), an efficient and scalable CH construction algorithm in parallel. To address the challenges in previous work, our improvements focus on both redesigning the algorithm and leveraging parallel data structures. We compare SPoCH with the state-of-the-art sequential and parallel implementations on 16 graphs of various types. Our experiments show that SPoCH achieves 11 11 – 68 × 68\times speedups over the best sequential baseline and 3.8 3.8 – 41 × 41\times speedups over the best parallel baseline in CH construction, while maintaining competitive query performance and CH graph size. We released our code and all datasets used in this paper. † † cc-license: by 1. Introduction Computing shortest distance is one of the most fundamental graph problems, playing a vital role in various applications, such as navigation on road networks. To accelerate point-to-point distance queries, many existing solutions use two-phase approaches, which preprocess the graph and construct an index—often an auxiliary graph—to facilitate queries. Among the most notable two-phase solutions is the Contraction Hierarchies (CH) ( Geisberger et al. 2008 ) , which is mainly designed for sparse networks such as road networks, and is widely used in practice, for instance in Google Maps. In addition to being used on its own, CH is also a vital component in other approaches for various applications on distance queries, such as Transit Node Routing ( Arz et al. 2013 ; Bast et al. 2006 ; Bast et al. 2007 ) , Hub-Based Labeling ( Abraham et al. 2011 ; Abraham et al. 2012 ; Delling et al. 2013a ) , and some renowned algorithms including CHASE ( Bauer et al. 2010 ) and PHAST ( Delling et al. 2013b ) . We refer the audience to the excellent surveys ( Sommer 2014 ; Bast et al. 2016 ; Madkour et al. 2017 ) for more background of the state-of-the-art techniques for route planning. Algorithms Preprocessing time Query time Dijkstra ( Dijkstra 1959 ) - 7.20 s \Delta -stepping ∗ ( Dong et al. 2024b ) - 0.320 s RoutingKit ( contributors 2024 ; Dibbelt et al. 2016 ) 2466 s 79.1 \mu s PHAST ( Group 2024 ; Delling et al. 2013b ) 1341 s 138 \mu s CH-Constructor ∗ ( Bühler and Nusser 2024 ) 1527 s 317 \mu s OSRM ∗ ( Luxen and Vetter 2024 ; Luxen and Vetter 2011 ) 307 s 163 \mu s Ours ∗ 23.1 s 93.3 \mu s Table 1. Preprocessing and point-to-point shortest path query time on the road network North America ( OpenStreetMap contributors 2010 ) . The graph has 87 million vertices and 113 million edges. 1 \mu s = 10^{-6} s. (*) denotes parallel implementations; others are sequential. The reported query time is the average across 1000 randomly selected pairs. Dijkstra ( Dijkstra 1959 ) and \Delta -stepping ( Dong et al. 2024b ) are sequential and parallel SSSP algorithms for comparison. In this paper, we consider a graph G=(V,E) with an edge weight function w:E\mapsto\mathbb{R}^{+} . Given two vertices s,t\in V , a distance query asks for the shortest distance from s to t . The idea of CH, as illustrated in fig. 1 (a), is to “contract” the graph into a hierarchy, which is an auxiliary graph \mathit{G_{\scriptsize\mbox{\it CH}}} that preserves the shortest distances in G , such that distance queries on \mathit{G_{\scriptsize\mbox{\it CH}}} can be much faster. In each iteration, one vertex u and all its edges are moved from the original graph to an auxiliary graph \mathit{G_{\scriptsize\mbox{\it CH}}} , forming a level in \mathit{G_{\scriptsize\mbox{\it CH}}} . Additionally, extra edges ( shortcuts ) are added to the original graph, forming the overlay graph {\mathit{G_{\scriptsize\mbox{\it O}}}} , to preserve the pairwise distances among the remaining vertices. Finally, all vertices in \mathit{G_{\scriptsize\mbox{\it CH}}} form the contraction hierarchies (CH) . A distance query requires a bidirectional search on \mathit{G_{\scriptsize\mbox{\it CH}}} . Empirically, a distance query on the CH touches far fewer vertices than in the original graph, thereby resulting in much faster query speed. As shown in table 1 , for the North American roadmap from OpenStreetMap ( OpenStreetMap contributors 2010 ) , queries can be 10^{3} – 10^{5} faster than directly using SSSP algorithms, such as Dijkstra ( Dijkstra 1959 ) and \Delta -stepping (a parallel SSSP algorithm) ( Meyer and Sanders 2003 ; Dong et al. 2021 ) . However, this impressive querying speed comes at a cost— constructing \mathit{G_{\scriptsize\mbox{\it CH}}} is expensive . Existing sequential solutions use 22–41 minutes, and the best parallel solutions need more than 300 seconds. Such long preprocessing time may require significant computational resources, and limit its adaptability to large graphs. Such running time is reasonable for a sequential algorithm—both RoutingKit ( Dibbelt et al. 2016 ) and PHAST ( Delling et al. 2013b ) take 100\times construction time than Dijkstra, which is acceptable considering the speedup for queries. However, the existing parallel CH algorithms are only 4.4\times faster than (sequential) PHAST even on a 96-core machine. The results indicate a significant gap, suggesting the potential for improvements in parallelism in CH construction algorithms. In this paper, we propose SPoCH ( S calable P arallelization o f C ontraction H ierarchies), which supports scalable and efficient contraction hierarchies construction with high parallelism without compromising the query performance. The performance gain is mainly from good parallelism and algorithmic improvements for sequential performance. Conceptually, parallelizing CH construction is not hard. In 2009, Vetter ( Vetter 2009 ) pointed out that vertices in an independent set (i.e., vertices that do not share edges) can be contracted in parallel, as illustrated in fig. 1 (b). However, despite being studied in many later papers ( Luxen and Vetter 2024 ; Luxen and Vetter 2011 ; Karimi et al. 2019 ; Karimi et al. 2020 ; Kieritz et al. 2010 ; Bühler and Nusser 2024 ) , we are unaware of scalable multicore CH implementations. In fact, constructing CH is a sophisticated process with intensive computation. Achieving good performance requires high parallelism in all steps and careful algorithmic design. We observe two major challenges. First, identifying the vertices to contract involves simulating contractions on many (if not most) vertices, which

Read the complete text