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).