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

Wei Hu, Zhao Song, Lin F. Yang +1

We consider the $k$-means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space $\{1,2,\dots ,\Delta {\}}^d$ can be dynamically inserted to o…