A Batched Hartigan's $k$-Means Clustering

Edward Raff, Michael SlawinskiarXiv 2026 · arXiv

Abstract

Hartigan's $k$-means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "$k$-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.
BibTeX
@misc{raff2026batched,
  author = {Edward Raff and Michael Slawinski},
  title = {{A Batched Hartigan's $k$-Means Clustering}},
  year = {2026},
  eprint = {2611.01207},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01207},
}

Loading related content...

Figure