Efficient Centroid-Linkage Clustering

2024/06/07 by MohammadHossein Bateni, Bateni, MohammadHossein, Laxman Dhulipala +11
Biochemistry, Genetics and Molecular Biology · #Bioinformatics and Genomic Networks #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2406.05066

openalex publication_date 2024/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a c-approximate clustering in roughly n^1+O(1/c2) 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× speedup due to performing fewer distance comparisons.

Related

• Parallel Hierarchical Agglomerative Clustering in Low Dimensions
• It's Hard to HAC with Average Linkage!
• Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
• ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
• Hierarchical Clustering better than Average-Linkage