An Algorithm for Online K-Means Clustering

Understand

This paper shows that one can be competitive with the k-means objective while operating online.

• In this model, the algorithm receives vectors v_1,...,v_n one by one in an arbitrary order.
• For each vector the algorithm outputs a cluster identifier before receiving the next one.
• Our online algorithm generates ~O(k) clusters whose k-means cost is ~O(W*).