Massively Parallel Algorithms for Approximate Shortest Paths
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_ | 1866913843451527168 |
|---|---|
| author | Dory, Michal Matar, Shaked |
| author_facet | Dory, Michal Matar, Shaked |
| contents | We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $poly(\log{\log{n}})$ rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with $n$ vertices and $m$ edges. Our first contribution is a $(1+ε)$-approximation algorithm for Single-Source Shortest Paths (SSSP) that takes $poly(\log{\log{n}})$ rounds in the near-linear MPC model, where the memory per machine is $\tilde{O}(n)$ and the total memory is $\tilde{O}(mn^ρ)$, where $ρ$ is a small constant. Our second contribution is a distance oracle that allows to approximate the distance between any pair of vertices. The distance oracle is constructed in $poly(\log{\log{n}})$ rounds and allows to query a $(1+ε)(2k-1)$-approximate distance between any pair of vertices $u$ and $v$ in $O(1)$ additional rounds. The algorithm is for the near-linear memory MPC model with total memory of size $\tilde{O}((m+n^{1+ρ})n^{1/k})$, where $ρ$ is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with $\tilde{O}(n)$ memory, where the rest of machines can have sublinear memory of size $O(n^γ)$ for a small constant $γ< 1$. All previous algorithms for approximate shortest paths in the near-linear MPC model either required $Ω(\log{n})$ rounds or had an $Ω(\log{n})$ approximation. Our approach is based on fast construction of near-additive emulators, limited-scale hopsets and limited-scale distance sketches that are tailored for the MPC model. While our end-results are for the near-linear MPC model, many of the tools we construct such as hopsets and emulators are constructed in the more restricted sublinear MPC model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_06952 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Massively Parallel Algorithms for Approximate Shortest Paths Dory, Michal Matar, Shaked Data Structures and Algorithms Distributed, Parallel, and Cluster Computing We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take $poly(\log{\log{n}})$ rounds in the near-linear memory MPC model. Our results are for unweighted undirected graphs with $n$ vertices and $m$ edges. Our first contribution is a $(1+ε)$-approximation algorithm for Single-Source Shortest Paths (SSSP) that takes $poly(\log{\log{n}})$ rounds in the near-linear MPC model, where the memory per machine is $\tilde{O}(n)$ and the total memory is $\tilde{O}(mn^ρ)$, where $ρ$ is a small constant. Our second contribution is a distance oracle that allows to approximate the distance between any pair of vertices. The distance oracle is constructed in $poly(\log{\log{n}})$ rounds and allows to query a $(1+ε)(2k-1)$-approximate distance between any pair of vertices $u$ and $v$ in $O(1)$ additional rounds. The algorithm is for the near-linear memory MPC model with total memory of size $\tilde{O}((m+n^{1+ρ})n^{1/k})$, where $ρ$ is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with $\tilde{O}(n)$ memory, where the rest of machines can have sublinear memory of size $O(n^γ)$ for a small constant $γ< 1$. All previous algorithms for approximate shortest paths in the near-linear MPC model either required $Ω(\log{n})$ rounds or had an $Ω(\log{n})$ approximation. Our approach is based on fast construction of near-additive emulators, limited-scale hopsets and limited-scale distance sketches that are tailored for the MPC model. While our end-results are for the near-linear MPC model, many of the tools we construct such as hopsets and emulators are constructed in the more restricted sublinear MPC model. |
| title | Massively Parallel Algorithms for Approximate Shortest Paths |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2412.06952 |