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 tilde O(k) in general metric spaces, which reduces to tilde O(d) in the Euclidean space ℝd. The query time is O(k2) in general metrics, and O(kd) in ℝ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 + k2). To maintain a O(polylog~k)-approximation, the query time is reduced to tilde O(kd).