Fully Dynamic k-Means Coreset in Near-Optimal Update Time
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917708202770432 |
|---|---|
| author | la Tour, Max Dupré Henzinger, Monika Saulpic, David |
| author_facet | la Tour, Max Dupré Henzinger, Monika Saulpic, David |
| contents | We study in this paper the problem of maintaining a solution to $k$-median and $k$-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of $\tilde O(k)$ in general metric spaces, which reduces to $\tilde O(d)$ in the Euclidean space $\mathbb{R}^d$. The query time is $O(k^2)$ in general metrics, and $O(kd)$ in $\mathbb{R}^d$.
To maintain a constant-factor approximation for $k$-median and $k$-means clustering in Euclidean space, this directly leads to an algorithm update time $\tilde O(d)$, and query time $\tilde O(kd + k^2)$. To maintain a $O(polylog~k)$-approximation, the query time is reduced to $\tilde O(kd)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19926 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic k-Means Coreset in Near-Optimal Update Time la Tour, Max Dupré Henzinger, Monika Saulpic, David Data Structures and Algorithms We study in this paper the problem of maintaining a solution to $k$-median and $k$-means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently maintain a coreset, a compressed version of the dataset, that allows easy computation of a clustering solution at query time. Our coreset algorithm has near-optimal update time of $\tilde O(k)$ in general metric spaces, which reduces to $\tilde O(d)$ in the Euclidean space $\mathbb{R}^d$. The query time is $O(k^2)$ in general metrics, and $O(kd)$ in $\mathbb{R}^d$. To maintain a constant-factor approximation for $k$-median and $k$-means clustering in Euclidean space, this directly leads to an algorithm update time $\tilde O(d)$, and query time $\tilde O(kd + k^2)$. To maintain a $O(polylog~k)$-approximation, the query time is reduced to $\tilde O(kd)$. |
| title | Fully Dynamic k-Means Coreset in Near-Optimal Update Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.19926 |