Summary: 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, \dots, 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 \gamma n)\) clusters whose expected \(k\)-means cost is \(O(W^\ast \log n)\). Here, \(W^\ast\) is the optimal \(k\)-means cost using \(k\) clusters and \(\gamma\) is the aspect ratio of the data. The dependence on \(\gamma\) 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.
For the entire collection see [Zbl 1331.68012].