On Parallel $k$-Center Clustering
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908976454565888 |
|---|---|
| author | Coy, Sam Czumaj, Artur Mishra, Gopinath |
| author_facet | Coy, Sam Czumaj, Artur Mishra, Gopinath |
| contents | 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 $δ\in (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 \ge Ω(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}(\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+o(1))$ clusters that is an ${O}(\log^*n)$-approximation for $k$-center. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_05883 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Parallel $k$-Center Clustering Coy, Sam Czumaj, Artur Mishra, Gopinath Data Structures and Algorithms 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 $δ\in (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 \ge Ω(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}(\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+o(1))$ clusters that is an ${O}(\log^*n)$-approximation for $k$-center. |
| title | On Parallel $k$-Center Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2304.05883 |