0

A Batched Hartigan's $k$-Means Clustering

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.

Open
Preview
Year
2026
ArXiv
arxiv.org/abs/2611.01207
Hosting
Abstract onlyARXIV-DEFAULT

Cite

Notes

Only stored in your browser.

Attribution

Abstract & full text
arxiv.org/abs/2611.01207ARXIV-DEFAULT
TL;DR
Semantic Scholar
Attribution policy →

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.