cs.LGOct 31, 2026

A Batched Hartigan's kk-Means Clustering

Authors: Edward Raff, Michael Slawinski

Organizations: CrowdStrike · University of Maryland, Baltimore County · Syracuse University

Abstract

Hartigan's kk-means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "kk-means". Yet, Hartigan's algorithm is far slower in practice due to its inherently sequential calculations. We devise a Batched Hartigan's method that enables vectorized calculation by exploiting the triangle inequality to expose a set of parallel-safe updates and a smaller set of sequential updates. This makes Hartigan's method competitive with Lloyd's in execution speed for the first time.

Figures & tables

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Apr 23, 2026

An effective variant of the Hartigan kk-means algorithm

The k-means problem is perhaps the classical clustering problem and often synonymous with Lloyd's algorithm (1957). It has become clear that Hartigan's algorithm (1975) gives better results in almost all cases, Telgarsky-Vattani note a typical improvement of 5%5\% -- 10%10\%. We point out that a very minor variation of Hartigan's method leads to another 2%2\% -- 5%5\% improvement; the improvement tends to become larger when either dimension or kk increase.
Nov 6, 2026

e-means: outperforming k-means (in one-tenth the epochs)

Lloyd's k-means algorithm is a long-running standard for clustering, with applications in data analysis, retrieval, quantization and data curation. In this paper, we introduce an exponential moving average optimization procedure for k-means with mini-batch updates, powered by modern deep learning machinery and new insights. We also establish scaling laws on how decay rate and batch size impact final performance. This gives us a formulaic rule to fix them for multiple problem sizes and embedding datasets, without the need for any hyperparameter sweep. The resulting clustering algorithm, coined e-means, is much faster than Lloyd k-means and converges to lower losses, frequently even beating k-means++. On a wide array of embeddings datasets, it beats the loss of Lloyd k-means at 25 epochs in 1.4 to 2.6 epochs, which translates to 10-45x GPU wall-clock speedups compared to state-of-the-art k-means implementations. As an example, e-means partitions DINO10B, a dataset of 10 billion DINO embeddings, into 16 million clusters in only 2.5 epochs, reaching a loss below Lloyd's at 25 epochs.
Jul 28, 2026

Lloyd's KK-Means Clustering Algorithm Is Frank-Wolfe in Disguise

Lloyd's KK-means algorithm, also known as naïve KK-means, is a widely used ad hoc optimization heuristic, designed to minimize the sum of squared errors (SSE) across all KK-partitions of a dataset via iterative cluster refinement. In this work, we establish a novel connection between Lloyd's algorithm and the Frank-Wolfe (FW) algorithm, a prominent first-order method for projection-free optimization. We demonstrate that Lloyd's algorithm is a special case of FW. Leveraging recent advances in FW methods for concave objectives, we derive a non-asymptotic O(1/t)\mathcal{O}(1/t) convergence rate to a local minimum of the SSE objective. To account for empty clusters, an outcome possible under Lloyd's greedy assignment, we develop an FW variant for semismooth objectives while retaining the same convergence rate that is solely controlled by the initial SSE value. We illustrate our findings with a simulation study for spherical Gaussian mixtures and a real-world image segmentation dataset.