$O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph
Connectivity, EMST and DBSCAN
$O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph
Connectivity, EMST and DBSCAN
In this paper, we investigate three fundamental problems in the Massively Parallel Computation (MPC) model: (i) grid graph connectivity, (ii) approximate Euclidean Minimum Spanning Tree (EMST), and (iii) approximate DBSCAN. Our first result is a $O(1)$-round Las Vegas (i.e., succeeding with high probability) MPC algorithm for computing the connected components …