# Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ℓp-Distances

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2017.

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

- [Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!](https://mlsanity.com/paper/2305.13560/) (2023)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Massively-Parallel Heat Map Sorting and Applications To Explainable Clustering](https://mlsanity.com/paper/2309.07486/) (2023)

## Abstract (arXiv)

We present massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of n input d-dimensional vectors under Hamming, ℓ1, ℓ2 and ℓ_∞ distances. All our algorithms run in O(log n) rounds of MPC for any fixed d and achieve (1+ε)-approximation for all distances (except Hamming for which we show an exact algorithm). We also show constant-factor inapproximability results for o(log n)-round algorithms under standard MPC hardness assumptions (for sufficiently large dimension depending on the distance used). Efficiency of implementation of our algorithms in Apache Spark is demonstrated through experiments on a variety of datasets exhibiting speedups of several orders of magnitude.