Flash-KMeans Outperforms Standard K-Means for Large Datasets

A new paper introduces Flash-KMeans, an exact K-Means implementation that is dramatically faster and more memory-efficient than standard approaches, enabling clustering of large-scale datasets.

Details

The classic Lloyd's algorithm for K-Means has three main steps: 1) compute distances from every point to every centroid, 2) assign each point to its nearest centroid, and 3) recompute centroids as the mean of assigned points. The distance computation in step 1 is the main bottleneck, as it requires O(n*k) distance calculations, where n is the number of data points and k is the number of clusters. Most implementations, including scikit-learn's, store intermediate results that can balloon memory usage, making it challenging to cluster large datasets with high-dimensional vectors. Flash-KMeans addresses these issues by applying techniques like tiled distance computation, fused assignment and reduction, and exploiting the triangle inequality to restructure the computation in a more cache-friendly and memory-efficient way. The result is an exact K-Means implementation that can achieve 5-16x speedups over optimized baselines while using a fraction of the memory. This is particularly impactful given the growing importance of clustering large-scale vector embeddings for applications like approximate nearest neighbor search, user behavior analysis, and data deduplication.