# Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 77 references that are in the map.
- First posted on arXiv 10 Feb 2025.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Squeeze-and-Excitation Networks](https://mlsanity.com/paper/1709.01507/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligence](https://mlsanity.com/paper/2002.04803/) (2020)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [A Survey on Locality Sensitive Hashing Algorithms and their Applications](https://mlsanity.com/paper/2102.08942/) (2021)
- [Survey of Vector Database Management Systems](https://mlsanity.com/paper/2310.14021/) (2023)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2408.08933/) (2024)
- [GGNN: Graph-based GPU Nearest Neighbor Search](https://mlsanity.com/paper/1912.01059/) (2019)
- [A Nearly Tight Analysis of Greedy k-means++](https://mlsanity.com/paper/2207.07949/) (2022)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [Fast Approximate K-Means via Cluster Closures](https://mlsanity.com/paper/1312.3061/) (2013)
- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [PQk-means: Billion-scale Clustering for Product-quantized Codes](https://mlsanity.com/paper/1709.03708/) (2017)
- [A True O(n logn)  Algorithm for the All-k-Nearest-Neighbors Problem](https://mlsanity.com/paper/1908.00159/) (2019)

## Abstract (arXiv)

For very large values of k, we consider methods for fast k-means clustering of massive datasets with 107~109 points in high-dimensions (d≥100). All current practical methods for this problem have runtimes at least Omega(k2). We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution.