A Scalable Algorithm for Single-Linkage Hierarchical Clustering on Distributed-Memory Architectures

Hierarchical clustering is a fundamental and widely-used clustering algorithm with many advantages over traditional partitional cluster-ing. Due to the explosion in size of modern scientific datasets, there is a pressing need for scalable analytics algorithms, but good scal-ing is difficult to achieve for hierarchical clustering due to data de-pendencies inherent in the algorithm. To the best of our knowledge, no previous work on parallel hierarchical clustering has shown scal-ability beyond a couple hundred processes. In this paper, we present PINK, a scalable parallel algorithm for single-linkage hierarchical clustering based on decomposing a problem instance into two dif-ferent types of subproblems. Despite the heterogeneous workloads, our algorithm exhibits good load balancing, as well as low memory requirements and a communication pattern that is both low-volume and deterministic. Evaluating PINK on up to 6050 processes, we find that it achieves speedups up to approximately 6600