Fully Dynamic k-Means Coreset in Near-Optimal Update Time

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 O(k) in general metric spaces, which reduces to O(d) in the Euclidean space Rᵈ. The query time is O(k²) in general metrics, and $O(kd)$ in Rᵈ. To maintain a constant-factor approximation for k-median and k-means clustering in Euclidean space, this directly leads to an algorithm update time O(d), and query time O(kd + k²). To maintain a $O(polylog~k)$-approximation, the query time is reduced to O(kd).