# Accelerating Spherical k-Means

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 26 references that are in the map.
- First posted on arXiv 8 Jul 2021.

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

- [Fast K-Means with Accurate Bounds](https://mlsanity.com/paper/1602.02514/) (2016)
- [ELKI: A large open-source library for data analysis - ELKI Release 0.7.5 "Heidelberg"](https://mlsanity.com/paper/1902.03616/) (2019)
- [BETULA: Numerically Stable CF-Trees for BIRCH Clustering](https://mlsanity.com/paper/2006.12881/) (2020)
- [Unsupervised Pathology Image Segmentation Using Representation Learning with Spherical K-means](https://mlsanity.com/paper/1804.03828/) (2018)

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

- [Stop using the elbow criterion for k-means and how to choose the number of clusters instead](https://mlsanity.com/paper/2212.12189/) (2022)
- [Robustness of shallow graph embedding methods for community detection](https://mlsanity.com/paper/2405.00636/) (2024)
- [Accelerating k-Means Clustering with Cover Trees](https://mlsanity.com/paper/2410.15117/) (2024)
- [On Projections to Linear Subspaces](https://mlsanity.com/paper/2209.12485/) (2022)
- [Accelerating spherical K-means clustering for large-scale sparse document data](https://mlsanity.com/paper/2411.11300/) (2024)

## Abstract (arXiv)

Spherical k-means is a widely used clustering algorithm for sparse and high-dimensional data such as document vectors. While several improvements and accelerations have been introduced for the original k-means algorithm, not all easily translate to the spherical variant: Many acceleration techniques, such as the algorithms of Elkan and Hamerly, rely on the triangle inequality of Euclidean distances. However, spherical k-means uses Cosine similarities instead of distances for computational efficiency. In this paper, we incorporate the Elkan and Hamerly accelerations to the spherical k-means algorithm working directly with the Cosines instead of Euclidean distances to obtain a substantial speedup and evaluate these spherical accelerations on real data.