Dual-tree k-means with bounded single-iteration runtime

K-means is a widely used clustering algorithm, but for k clusters and a dataset size of N, each iteration of Lloyd's algorithm costs O(kN) time. Although there are tree-based techniques to accelerate single Lloyd iterations, none of these techniques are tailored to the case of large k, which is increasingly common as dataset sizes grow. We propose a dual-tree algorithm that gives the exact result of Lloyd iterations; when using cover trees, we are able to bound the worst-case runtime of each algorithm as O(N + k log k) (this bound also depends on dataset-dependent quantities). To our knowledge these are the first sub-O(kN) bounds for exact Lloyd iterations. We then show that these theoretically favorable algorithms significantly outperform other approaches in practice, especially for large N and k.