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

Code

• github.com/jacketsj/mopbucket
  Officialnone★ 1

Abstract

For very large values of k, we consider methods for fast k-means clustering of massive datasets with 10^710^9 points in high-dimensions (d100). All current practical methods for this problem have runtimes at least (k^2). 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.

Reproductions