View article

This paper shows that one can be competitive with the k-means objective while operating online. In this model, the algorithm receives vectors v₁, …, v_n one by one in an arbitrary order. For each vector v_t the algorithm outputs a cluster identifier before receiving v_t+1. Our online algorithm generates O(k log n log γn) clusters whose expected k-means cost is O(W* log n). Here, W* is the optimal k-means cost using k clusters and γ is the aspect ratio of the data. The dependence on γ is shown to be unavoidable and tight. We also show that, experimentally, it is not much worse than k-means++ while operating in a strictly more constrained computational model.