# Accelerating k-Means Clustering with Cover Trees

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 24 references that are in the map.
- First posted on arXiv 19 Oct 2024.

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

- [Stop using the elbow criterion for k-means and how to choose the number of clusters instead](https://mlsanity.com/paper/2212.12189/) (2022)
- [A Triangle Inequality for Cosine Similarity](https://mlsanity.com/paper/2107.04071/) (2021)
- [Fast K-Means with Accurate Bounds](https://mlsanity.com/paper/1602.02514/) (2016)
- [Accelerating Spherical k-Means](https://mlsanity.com/paper/2107.04074/) (2021)

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

- [A Super Fast K-means for Indexing Vector Embeddings](https://mlsanity.com/paper/2603.20009/) (2026)

## Abstract (arXiv)

The k-means clustering algorithm is a popular algorithm that partitions data into k clusters. There are many improvements to accelerate the standard algorithm. Most current research employs upper and lower bounds on point-to-cluster distances and the triangle inequality to reduce the number of distance computations, with only arrays as underlying data structures. These approaches cannot exploit that nearby points are likely assigned to the same cluster. We propose a new k-means algorithm based on the cover tree index, that has relatively low overhead and performs well, for a wider parameter range, than previous approaches based on the k-d tree. By combining this with upper and lower bounds, as in state-of-the-art approaches, we obtain a hybrid algorithm that combines the benefits of tree aggregation and bounds-based filtering.