arXiv preprint ·
Improved Massively Parallel Shortest Path Computation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an $a$-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex $u \in V$, the oracle returns $a$-approximate distances $δ(u,v)$ for all $v \in V$. Fix an $n$-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has $\tildeΘ(n)$ memory, and the heterogeneous regime, where all machines have $Θ(n^γ)$ memory for some constant $γ\in (0,1]$, except for a single machine with $\tildeΘ(n)$ memory. We develop randomised algorithms that construct $O(1)$-approximate SSSP oracles in $O(\log\log n)$ rounds in the near-linear regime and in $O(\log^2\log n)$ rounds in the heterogeneous regime. These oracles answer distance queries in $O(1)$ rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total memory, requires $\left(\log\log n\right)^{2+O(1/γ)}$ rounds and applies only to unweighted graphs in the heterogeneous setting. We say that $\tilde N_k(u)$ is the approximate $k$-nearest neighbourhood of a vertex $u$ if there exists an approximate distance estimate $δ$ such that $\tilde N_k(u)$ consists of the $k$ vertices closest to $u$ according to $δ$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(γ)}$-nearest neighbourhoods in the heterogeneous MPC model in $O(\log^2\log n)$ rounds.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Distributed & Parallel Computing
Federated Coreset Subsampling for Distributed Memory Banks
ATTUNE: Agentic Throughput Tuning for LLM Training
Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds
DisaggKD: Efficient Knowledge Distillation through Teacher-Student Disaggregation and a Fused Loss
Prorsa: Unleashing the Potential of Prefill-Decode Disaggregation in Agentic Reinforcement Learning
Get the few papers worth your time in Distributed & Parallel Computing every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.