Parallel Contraction Hierarchies Can Be Efficient and Scalable
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913805152288768 |
|---|---|
| author | Wan, Zijin Dong, Xiaojun Wang, Letong Zhu, Enzuo Gu, Yan Sun, Yihan |
| author_facet | Wan, Zijin Dong, Xiaojun Wang, Letong Zhu, Enzuo Gu, Yan Sun, Yihan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_18008 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parallel Contraction Hierarchies Can Be Efficient and Scalable Wan, Zijin Dong, Xiaojun Wang, Letong Zhu, Enzuo Gu, Yan Sun, Yihan Data Structures and Algorithms Distributed, Parallel, and Cluster Computing 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. |
| title | Parallel Contraction Hierarchies Can Be Efficient and Scalable |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2412.18008 |