  We consider online $k$-means clustering where each new point is assigned to
the nearest cluster center, after which the algorithm may update its centers.
The loss incurred is the sum of squared distances from new points to their
assigned cluster centers. The goal over a data stream $X$ is to achieve loss
that is a constant factor of $L(X, OPT_k)$, the best possible loss using $k$
fixed points in hindsight.
  We propose a data parameter, $\Lambda(X)$, such that for any algorithm
maintaining $O(k\text{poly}(\log n))$ centers at time $n$, there exists a data
stream $X$ for which a loss of $\Omega(\Lambda(X))$ is inevitable.
  We then give a randomized algorithm that achieves clustering loss
$O(\Lambda(X) + L(X, OPT_k))$. Our algorithm uses $O(k\text{poly}(\log n))$
memory and maintains $O(k\text{poly}(\log n))$ cluster centers. Our algorithm
also enjoys a running time of $O(k\text{poly}(\log n))$ and is the first
algorithm to achieve polynomial space and time complexity in this setting. It
also is the first to have provable guarantees without making any assumptions on
the input data.
