# Exact Acceleration of K-Means++ and K-Means|

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

## Key facts

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

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

- [Fast K-Means with Accurate Bounds](https://mlsanity.com/paper/1602.02514/) (2016)
- [Tree-Independent Dual-Tree Algorithms](https://mlsanity.com/paper/1304.4327/) (2013)
- [Getting Passive Aggressive About False Positives: Patching Deployed Malware Detectors](https://mlsanity.com/paper/2010.12080/) (2020)
- [K-Medoids For K-Means Seeding](https://mlsanity.com/paper/1609.04723/) (2016)
- [Toward Metric Indexes for Incremental Insertion and Querying](https://mlsanity.com/paper/1801.05055/) (2018)

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

- [Deploying Convolutional Networks on Untrusted Platforms Using 2D Holographic Reduced Representations](https://mlsanity.com/paper/2206.05893/) (2022)
- [Accelerating the k-means++ Algorithm by Using Geometric Information](https://mlsanity.com/paper/2408.13189/) (2024)

## Abstract (arXiv)

K-Means++ and its distributed variant K-Means| have become de facto tools for selecting the initial seeds of K-means. While alternatives have been developed, the effectiveness, ease of implementation, and theoretical grounding of the K-means++ and | methods have made them difficult to "best" from a holistic perspective. By considering the limited opportunities within seed selection to perform pruning, we develop specialized triangle inequality pruning strategies and a dynamic priority queue to show the first acceleration of K-Means++ and K-Means| that is faster in run-time while being algorithmicly equivalent. For both algorithms we are able to reduce distance computations by over 500×. For K-means++ this results in up to a 17× speedup in run-time and a 551× speedup for K-means|. We achieve this with simple, but carefully chosen, modifications to known techniques which makes it easy to integrate our approach into existing implementations of these algorithms.