# Scaling Hierarchical Agglomerative Clustering to Billion-sized Datasets

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 21 references that are in the map.
- First posted on arXiv 25 May 2021.

## Builds on (most cited first, 1 of 1)

- [Local algorithms for interactive clustering](https://mlsanity.com/paper/1312.6724/) (2013)

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

- [Batch Active Learning at Scale](https://mlsanity.com/paper/2107.14263/) (2021)
- [Bamboo: Building Mega-Scale Vision Dataset Continually with Human-Machine Synergy](https://mlsanity.com/paper/2203.07845/) (2022)
- [Introducing the NewsPaLM MBR and QE Dataset: LLM-Generated High-Quality Parallel Data Outperforms Traditional Web-Crawled Data](https://mlsanity.com/paper/2408.06537/) (2024)
- [Analyzing Similarity Metrics for Data Selection for Language Model Pretraining](https://mlsanity.com/paper/2502.02494/) (2025)
- [AICCA: AI-driven Cloud Classification Atlas](https://mlsanity.com/paper/2209.15096/) (2022)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Hierarchical clustering with dot products recovers hidden tree structure](https://mlsanity.com/paper/2305.15022/) (2023)
- [Hierarchical Level-Wise News Article Clustering via Multilingual Matryoshka Embeddings](https://mlsanity.com/paper/2506.00277/) (2025)
- [ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain](https://mlsanity.com/paper/2106.04727/) (2021)
- [Compressing Search with Language Models](https://mlsanity.com/paper/2407.00085/) (2024)
- [SharedRequest: Privacy-Preserving Model-Agnostic Inference for Large Language Models](https://mlsanity.com/paper/2606.05004/) (2026)

## Abstract (arXiv)

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.