# Scalable Hierarchical Agglomerative Clustering

arXiv: https://arxiv.org/abs/2010.11821 · HTML: https://mlsanity.com/paper/2010.11821/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2020.

## Built on by (most cited first, 13 of 13)

- [AICCA: AI-driven Cloud Classification Atlas](https://mlsanity.com/paper/2209.15096/) (2022)
- [On the cohesion and separability of average-link for hierarchical agglomerative clustering](https://mlsanity.com/paper/2411.05097/) (2024)
- [Hierarchical Level-Wise News Article Clustering via Multilingual Matryoshka Embeddings](https://mlsanity.com/paper/2506.00277/) (2025)
- [Are "Hierarchical" Visual Representations Hierarchical?](https://mlsanity.com/paper/2311.05784/) (2023)
- [Probing clustering in neural network representations](https://mlsanity.com/paper/2311.07864/) (2023)
- [A Clustering Method with Graph Maximum Decoding Information](https://mlsanity.com/paper/2403.13846/) (2024)
- [The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering](https://mlsanity.com/paper/2411.10290/) (2024)
- [A multi-dimensional unsupervised machine learning framework for clustering residential heat load profiles](https://mlsanity.com/paper/2411.16701/) (2024)
- [Hyperoctant Search Clustering: A Method for Clustering Data in High-Dimensional Hyperspheres](https://mlsanity.com/paper/2503.07917/) (2025)
- [Tree-Guided L1-Convex Clustering](https://mlsanity.com/paper/2503.24012/) (2025)
- [Rethinking Divisive Hierarchical Clustering from a Distributional Perspective](https://mlsanity.com/paper/2601.19718/) (2026)
- [Chamfer-Linkage for Hierarchical Agglomerative Clustering](https://mlsanity.com/paper/2602.10444/) (2026)
- [Refining Heuristic-Based Bitcoin Address Clustering with Graph Neural Networks](https://mlsanity.com/paper/2609.01942/) (2026)

## Abstract (arXiv)

The applicability of agglomerative clustering, for inferring both hierarchical and flat clustering, is limited by its scalability. Existing scalable hierarchical clustering methods sacrifice quality for speed and often lead to over-merging of clusters. In this paper, we present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points. We perform a detailed theoretical analysis, showing that under mild separability conditions our algorithm can not only recover the optimal flat partition, but also provide a two-approximation to non-parametric DP-Means objective. This introduces a novel application of hierarchical clustering as an approximation algorithm for the non-parametric clustering objective. We additionally relate our algorithm to the classic hierarchical agglomerative clustering method. We perform extensive empirical experiments in both hierarchical and flat clustering settings and show that our proposed approach achieves state-of-the-art results on publicly available clustering benchmarks. Finally, we demonstrate our method's scalability by applying it to a dataset of 30 billion queries. Human evaluation of the discovered clusters show that our method finds better quality of clusters than the current state-of-the-art.