Efficient Centroid-Linkage Clustering
<|reference_start|>Efficient Centroid-Linkage Clustering: We give an efficient 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.<|reference_end|>
@article{bateni2024efficient,
    title={Efficient Centroid-Linkage Clustering},
    author={MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N
  Gowda, D Ellis Hershkowitz, Rajesh Jayaram, Jakub {L}k{a}cki},
    journal={arXiv preprint arXiv:2406.05066},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.05066},
    primaryClass={cs.DS}
}