Efficient Centroid-Linkage Clustering
Mohammadhossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, D Ellis Hershkowitz, Rajesh Jayaram, Jakub Lacki
Abstract
We give an algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a $c$-approximate clustering in roughly $n^{1+O(1/c^2)}$ time. We obtain our result by combining a new centroid-linkage HAC algorithm with a novel fully dynamic data structure for nearest neighbor search which works under adaptive updates. We also evaluate our algorithm empirically. By leveraging a state-of-the-art nearest-neighbor search library, we obtain a fast and accurate centroid-linkage HAC algorithm. Compared to an existing state-of-the-art exact baseline, our implementation maintains the clustering quality while delivering up to a $36\times$ speedup due to performing fewer distance comparisons.
BibTeX
@inproceedings{
bateni2024efficient,
title={Efficient Centroid-Linkage Clustering},
author={Mohammadhossein Bateni and Laxman Dhulipala and Willem Fletcher and Kishen N Gowda and D Ellis Hershkowitz and Rajesh Jayaram and Jakub Lacki},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=5VE1iLeYOz}
}