# An Algorithm for Online K-Means Clustering

arXiv: https://arxiv.org/abs/1412.5721 · HTML: https://mlsanity.com/paper/1412.5721/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2014.

## Built on by (most cited first, 12 of 12)

- [Illiterate DALL-E Learns to Compose](https://mlsanity.com/paper/2110.11405/) (2021)
- [Optimal Clustering with Bandit Feedback](https://mlsanity.com/paper/2202.04294/) (2022)
- [Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining](https://mlsanity.com/paper/2303.15311/) (2023)
- [A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering](https://mlsanity.com/paper/2102.04050/) (2021)
- [Online k-means Clustering on Arbitrary Data Streams](https://mlsanity.com/paper/2102.09101/) (2021)
- [Efficient Large-Scale Face Clustering Using an Online Mixture of Gaussians](https://mlsanity.com/paper/2103.17272/) (2021)
- [Learning from Streaming Data when Users Choose](https://mlsanity.com/paper/2406.01481/) (2024)
- [Online Clustering of Data Sequences with Bandit Information](https://mlsanity.com/paper/2501.11421/) (2025)
- [Airplane Type Identification Based on Mask RCNN and Drone Images](https://mlsanity.com/paper/2108.12811/) (2021)
- [Margin-Independent Online Multiclass Learning via Convex Geometry](https://mlsanity.com/paper/2111.08057/) (2021)
- [Incremental Gaussian Mixture Clustering for Data Streams](https://mlsanity.com/paper/2412.07217/) (2024)
- [Efficient Clustering in Stochastic Bandits](https://mlsanity.com/paper/2601.09162/) (2026)

## Abstract (arXiv)

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*). Here, W* is the optimal k-means cost using k clusters and ~O suppresses poly-logarithmic factors. We also show that, experimentally, it is not much worse than k-means++ while operating in a strictly more constrained computational model.