# Fast and Accurate k-means++ via Rejection Sampling

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Dec 2020.

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

- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond](https://mlsanity.com/paper/2402.17327/) (2024)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [A Faster k-means++ Algorithm](https://mlsanity.com/paper/2211.15118/) (2022)
- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [An Analysis of Dα seeding for k-means](https://mlsanity.com/paper/2310.13474/) (2023)
- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)
- [Accelerating the k-means++ Algorithm by Using Geometric Information](https://mlsanity.com/paper/2408.13189/) (2024)
- [Coreset Spectral Clustering](https://mlsanity.com/paper/2503.07227/) (2025)

## Abstract (arXiv)

k-means++ citearthur2007k is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide adoption, k-means++ sometimes suffers from being slow on large data-sets so a natural question has been to obtain more efficient algorithms with similar guarantees. In this paper, we present a near linear time algorithm for k-means++ seeding. Interestingly our algorithm obtains the same theoretical guarantees as k-means++ and significantly improves earlier results on fast k-means++ seeding. Moreover, we show empirically that our algorithm is significantly faster than k-means++ and obtains solutions of equivalent quality.