---
title: "A Batched Hartigan's $k$-Means Clustering"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.01207v1"
permalink: "https://feed.astralor.com/items/itm_b30073986c90a807e892cab7"
published: "2026-10-31T18:59:34.000Z"
score: 50
channel: "ai"
tags: ["Batched Hartigan","Means Clustering Hartigan","Lloyd","Yet","Hartigan"]
---

# A Batched Hartigan's $k$-Means Clustering

## At a glance

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 sequen…

## Key points

- 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.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_b30073986c90a807e892cab7