Nearly Optimal Dynamic k-Means Clustering for High-Dimensional Data

Abstract

We consider the k-means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space \1, 2, , \^d can be dynamically inserted to or deleted from the dataset. For this problem, we provide a one-pass coreset construction algorithm using space O(k poly(d, )), where k is the target number of centers. To our knowledge, this is the first dynamic geometric data stream algorithm for k-means using space polynomial in dimension and nearly optimal (linear) in k.

Tasks

Reproductions