Scaling Hierarchical Agglomerative Clustering to Billion-sized Datasets
This addresses the challenge of scaling HAC to large datasets for researchers and practitioners in data mining and machine learning, representing a significant advancement rather than an incremental improvement.
The paper tackles the scalability problem of Hierarchical Agglomerative Clustering (HAC) by proposing a distributed algorithm called Reciprocal Agglomerative Clustering (RAC), which recovers the exact HAC solution and can process billions of data points with trillions of edges in under an hour.
Hierarchical Agglomerative Clustering (HAC) is one of the oldest but still most widely used clustering methods. However, HAC is notoriously hard to scale to large data sets as the underlying complexity is at least quadratic in the number of data points and many algorithms to solve HAC are inherently sequential. In this paper, we propose {Reciprocal Agglomerative Clustering (RAC)}, a distributed algorithm for HAC, that uses a novel strategy to efficiently merge clusters in parallel. We prove theoretically that RAC recovers the exact solution of HAC. Furthermore, under clusterability and balancedness assumption we show provable speedups in total runtime due to the parallelism. We also show that these speedups are achievable for certain probabilistic data models. In extensive experiments, we show that this parallelism is achieved on real world data sets and that the proposed RAC algorithm can recover the HAC hierarchy on billions of data points connected by trillions of edges in less than an hour.