On Parallel k-Center Clustering
On Parallel k-Center Clustering
复制标题
关于并行 k 中心聚类
DOI：
10.1145/3558481.3591075
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Coy S
中科院分区：
文献类型：
--
作者：
Coy S
我们在低局部空间大规模并行计算 (MPC) 模型上考虑并行设置中的经典 k 中心问题，每台机器的局部空间为 O (nδ)，其中 δ ∈ (0,1) 是任意常数。作为一个中心聚类问题，k中心问题得到了广泛的研究。尽管如此，直到最近，所有并行 MPC 算法都需要每台机器 Ω(k) 甚至 Ω(knδ) 本地空间。虽然此设置涵盖了 k 值较小的情况，但对于大量集群，这些算法需要大量本地内存，从而导致其可扩展性较差。 Bateni 等人最近在低局部空间 MPC 模型中考虑了大 k,k ≥ Ω(nδ) 的情况。 (2021)，他给出了一个 O (log log n) 轮 MPC 算法，该算法产生 k(1 + ο (1)) 个中心，其成本乘法近似为 O (log log log n)。在本文中，我们扩展了 Bateni 等人的算法。并设计一种低局部空间 MPC 算法，该算法在 O (log log n) 轮中返回具有 k(1 + ο(1)) 簇的聚类，该簇是 k 中心的 O (log*n) 近似值。
We consider the classic k-center problem in a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model, with local space per machine of O (nδ), where δ ∈ (0,1) is an arbitrary constant. As a central clustering problem, the k-center problem has been studied extensively. Still, until very recently, all parallel MPC algorithms have been requiring Ω(k) or even Ω(knδ) local space per machine. While this setting covers the case of small values of k, for a large number of clusters these algorithms require large local memory, making them poorly scalable. The case of large k,k ≥ Ω(nδ), has been considered recently for the low-local-space MPC model by Bateni et al. (2021), who gave an O (log log n)-round MPC algorithm that produces k(1 + ο (1)) centers whose cost has multiplicative approximation of O (log log log n). In this paper we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in O (log log n) rounds returns a clustering with k(1 + ο(1)) clusters that is an O (log*n)-approximation for k-center.
影响因子：
2.5
作者：
Ceccarello, Matteo;Pietracaprina, Andrea;Pucci, Geppino
通讯作者：
Pucci, Geppino