On Parallel k-Center Clustering

2023/04/12 by Sam Coy, Coy, Sam, Artur Czumaj +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2304.05883

openalex publication_date 2023/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the classic k-center problem in the constant dimensional Euclidean space under 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 Ω(k n^δ) 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+o(1)) centers whose cost has multiplicative approximation of O(logloglog n). In this paper we extend the algorithm of Bateni et al. and design a low-local-space MPC algorithm that in O(loglog n) rounds returns a clustering with k(1+o(1)) clusters that is an O(log^*n)-approximation for k-center.

Cited by

• Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond

Related

• Fully Scalable MPC Algorithms for Euclidean k-Center
• Efficient Parallel Algorithms for k-Center Clustering
• Fully Scalable MPC Algorithms for Clustering in High Dimension
• k-Center Clustering with Outliers in the MPC and Streaming Model
• Solving k-center Clustering (with Outliers) in MapReduce and\n Streaming, almost as Accurately as Sequentially