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

2025/02/10 by Jack Spalding-Jamieson, Spalding-Jamieson, Jack, Eliot W. Robson +3
Computer Science · #Face and Expression Recognition #Data Management and Algorithms #Advanced Clustering Algorithms Research

paper · pdf · doi:10.48550/arxiv.2502.06163

Abstract

For very large values of k, we consider methods for fast k-means clustering of massive datasets with 10⁷∼10⁹ points in high-dimensions (d≥100). All current practical methods for this problem have runtimes at least Ω(k²). 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.

Related

• Fast k-means based on KNN Graph
• k2-means for fast and accurate large scale clustering
• An efficient K -means clustering algorithm for massive data
• Fully Scalable MPC Algorithms for Clustering in High Dimension
• Scalable Initialization Methods for Large-Scale Clustering