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

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.