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

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

    Nov 6, 2026Swann Bessa, Pierre-Emmanuel Mazaré, Gergely Szilvasy +4ClusteringScaling Laws

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

    Jul 28, 2026Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-JulienClusteringUnsupervised Clustering