# Fast K-Means with Accurate Bounds

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2016.

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

- [Accelerating Spherical k-Means](https://mlsanity.com/paper/2107.04074/) (2021)
- [A sampling-based approach for efficient clustering in large datasets](https://mlsanity.com/paper/2112.14793/) (2021)
- [Exact Acceleration of K-Means++ and K-Means|](https://mlsanity.com/paper/2105.02936/) (2021)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)
- [Accelerating k-Means Clustering with Cover Trees](https://mlsanity.com/paper/2410.15117/) (2024)
- [Structured Inverted-File k-Means Clustering for High-Dimensional Sparse Data](https://mlsanity.com/paper/2103.16141/) (2021)
- [Systematically and efficiently improving k-means initialization by pairwise-nearest-neighbor smoothing](https://mlsanity.com/paper/2202.03949/) (2022)
- [Accelerating the k-means++ Algorithm by Using Geometric Information](https://mlsanity.com/paper/2408.13189/) (2024)
- [Accelerating spherical K-means clustering for large-scale sparse document data](https://mlsanity.com/paper/2411.11300/) (2024)
- [Two-Point Local Optimality in k-Means via Boundary-Point Screening](https://mlsanity.com/paper/2610.06182/) (2026)

## Abstract (arXiv)

We propose a novel accelerated exact k-means algorithm, which performs better than the current state-of-the-art low-dimensional algorithm in 18 of 22 experiments, running up to 3 times faster. We also propose a general improvement of existing state-of-the-art accelerated exact k-means algorithms through better estimates of the distance bounds used to reduce the number of distance calculations, and get a speedup in 36 of 44 experiments, up to 1.8 times faster. We have conducted experiments with our own implementations of existing methods to ensure homogeneous evaluation of performance, and we show that our implementations perform as well or better than existing available implementations. Finally, we propose simplified variants of standard approaches and show that they are faster than their fully-fledged counterparts in 59 of 62 experiments.