mlsanityData to 14 Oct 2026

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

arXiv 2502.06163 ↗First posted 10 Feb 2025cs.LG cs.CG stat.MLcited by 0

Not on the map. Why?

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.

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

30 of 77 references.

References · 30

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  2. 2017Squeeze-and-Excitation Networkscited by 4,789
  3. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,375
  4. 2020Dense Passage Retrieval for Open-Domain Question Answeringcited by 3,824
  5. 2017Billion-scale similarity search with GPUscited by 2,497
  6. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
  7. 2024The Faiss librarycited by 376
  8. 2018ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithmscited by 130
  9. 2017Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphcited by 104
  10. 2020Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligencecited by 82
  11. 2021A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Searchcited by 82
  12. 2022Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Searchcited by 45
18 more
  1. 2021A Survey on Locality Sensitive Hashing Algorithms and their Applicationscited by 40
  2. 2023Survey of Vector Database Management Systemscited by 39
  3. 2018Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighborscited by 37
  4. 2015The Hardness of Approximation of Euclidean k-meanscited by 25
  5. 2023ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithmscited by 24
  6. 2023CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUscited by 22
  7. 2024Results of the Big ANN: NeurIPS'23 competitioncited by 22
  8. 2023Similarity search in the blink of an eye with compressed indicescited by 21
  9. 2023Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitationscited by 20
  10. 2016Local Search Yields a PTAS for k-Means in Doubling Metricscited by 13
  11. 2024RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Searchcited by 12
  12. 2019GGNN: Graph-based GPU Nearest Neighbor Searchcited by 10
  13. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  14. 2023Multi-Swap k-Means++cited by 5
  15. 2013Fast Approximate K-Means via Cluster Closurescited by 3
  16. 2023PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Searchcited by 3
  17. 2017PQk-means: Billion-scale Clustering for Product-quantized Codescited by 2
  18. 2019A True O(n logn) Algorithm for the All-k-Nearest-Neighbors Problemcited by 2

Built on by

Not cited yet.