标题： $O(1)$-多维网格图连通性、EMST和DBSCAN的回合MPC算法 显示英文标题

标题： $O(1)$-Round MPC Algorithms for Multi-dimensional Grid Graph Connectivity, EMST and DBSCAN

摘要： 在本文中，我们研究了大规模并行计算（MPC）模型中的三个基本问题：（i）网格图连通性，（ii）近似欧几里得最小生成树（EMST），以及（iii）近似DBSCAN。我们的第一个结果是一个$O(1)$轮拉斯维加斯（即以高概率成功）的MPC算法，用于计算$d$维$c$穿透网格图（$(d,c)$网格图）上的连通分量，其中$d$和$c$都是正整数常量。 在这种网格图中，每个顶点都是$\mathbb{N}^d$中的整数坐标点，且只能在两个不同顶点之间的$\ell_\infty$-范数最多为$c$的情况下存在边。 据我们所知，目前在MPC模型中计算$(d,c)$-网格图的连通分量（CC's）的最佳现有结果是运行为通用图设计的最先进的MPC CC算法：它们分别达到$O(\log \log n + \log D)$[FOCS19]和$O(\log \log n + \log \frac{1}{\lambda})$[PODC19]轮次，其中$D$是{\em 直径}，$\lambda$是图的{\em 谱隙}。 使用我们的网格图连通性技术，我们的第二个主要结果是计算近似欧几里得最小生成树的$O(1)$轮拉斯维加斯 MPC 算法。 此问题现有的最先进结果是 Andoni 等人提出的$O(1)$轮 MPC 算法 [STOC14]，该算法仅在期望情况下保证整体权重的近似值。 相比之下，我们的算法不仅保证了确定性的整体权重近似，还实现了确定性的边级权重近似。后一种特性对许多应用至关重要，例如寻找双色最近邻和 DBSCAN 聚类。 最后但同样重要的是，我们的第三个主要结果是在$O(1)$维空间中计算近似 DBSCAN 聚类的$O(1)$轮拉斯维加斯 MPC 算法。 显示英文摘要

摘要： 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 on a $d$-dimensional $c$-penetration grid graph ($(d,c)$-grid graph), where both $d$ and $c$ are positive integer constants. In such a grid graph, each vertex is a point with integer coordinates in $\mathbb{N}^d$, and an edge can only exist between two distinct vertices with $\ell_\infty$-norm at most $c$. To our knowledge, the current best existing result for computing the connected components (CC's) on $(d,c)$-grid graphs in the MPC model is to run the state-of-the-art MPC CC algorithms that are designed for general graphs: they achieve $O(\log \log n + \log D)$[FOCS19] and $O(\log \log n + \log \frac{1}{\lambda})$[PODC19] rounds, respectively, where $D$ is the {\em diameter} and $\lambda$ is the {\em spectral gap} of the graph. With our grid graph connectivity technique, our second main result is a $O(1)$-round Las Vegas MPC algorithm for computing approximate Euclidean MST. The existing state-of-the-art result on this problem is the $O(1)$-round MPC algorithm proposed by Andoni et al.[STOC14], which only guarantees an approximation on the overall weight in expectation. In contrast, our algorithm not only guarantees a deterministic overall weight approximation, but also achieves a deterministic edge-wise weight approximation.The latter property is crucial to many applications, such as finding the Bichromatic Closest Pair and DBSCAN clustering. Last but not the least, our third main result is a $O(1)$-round Las Vegas MPC algorithm for computing an approximate DBSCAN clustering in $O(1)$-dimensional space.