2024/12/09 by Michal Dory, Dory, Michal, Shaked Matar +1
Computer Science · #Data Management and Algorithms #Advanced Database Systems and Queries #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2412.06952
We present fast algorithms for approximate shortest paths in the massively parallel computation (MPC) model. We provide randomized algorithms that take poly(loglogn) 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(loglogn) rounds in the near-linear MPC model, where the memory per machine is O(n) and the total memory is 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(loglogn) 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 O((m+n1+ρ)n1/k), where ρ is a small constant. While our algorithms are for the near-linear MPC model, in fact they only use one machine with 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 Ω(logn) rounds or had an Ω(logn) 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.