Papers › Parallel Contraction Hierarchies Can Be Efficient and Scalable
Parallel Contraction Hierarchies Can Be Efficient and Scalable
Zijin Wan, Xiaojun Dong, Letong Wang, Enzuo Zhu, Yan Gu, Yihan Sun
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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 (Scalable Parallelization of Contraction Hierarchies), 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 speedups of 11 to 68 times over the best sequential baseline and 3.8 to 41 times over the best parallel baseline in CH construction, while maintaining competitive query performance and CH graph size. We have released our code and all datasets used in this paper.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections