# Online k-means Clustering on Arbitrary Data Streams

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 33 references that are in the map.
- First posted on arXiv 18 Feb 2021.

## Builds on (most cited first, 6 of 6)

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Online k-means Clustering](https://mlsanity.com/paper/1909.06861/) (2019)
- [An Algorithm for Online K-Means Clustering](https://mlsanity.com/paper/1412.5721/) (2014)
- [Sequential no-Substitution k-Median-Clustering](https://mlsanity.com/paper/1905.12925/) (2019)
- [No-substitution k-means Clustering with Adversarial Order](https://mlsanity.com/paper/2012.14512/) (2020)
- [A Constant Approximation Algorithm for Sequential Random-Order No-Substitution k-Median Clustering](https://mlsanity.com/paper/2102.04050/) (2021)

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

- [Inference with K-means](https://mlsanity.com/paper/2410.17256/) (2024)
- [From a Static Multi-Level Small Semantic Codebook to a Dynamic Single-Level Large Semantic Codebook for Generative Recommendation](https://mlsanity.com/paper/2608.21012/) (2026)

## Abstract (arXiv)

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, OPTk), the best possible loss using k fixed points in hindsight. We propose a data parameter, Lambda(X), such that for any algorithm maintaining O(kpoly(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, OPTk)). Our algorithm uses O(kpoly(log n)) memory and maintains O(kpoly(log n)) cluster centers. Our algorithm also enjoys a running time of O(kpoly(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.