Nearly Optimal Dynamic $k$-Means Clustering for High-Dimensional Data
  We consider the $k$-means clustering problem in the dynamic streaming
setting, where points from a discrete Euclidean space $\{1, 2, \ldots,
\Delta\}^d$ can be dynamically inserted to or deleted from the dataset. For
this problem, we provide a one-pass coreset construction algorithm using space
$\tilde{O}(k\cdot \mathrm{poly}(d, \log\Delta))$, 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$.
