Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under ${\ell }_p$-Distances

Abstract

We present massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of $n$ input $d$-dimensional vectors under Hamming, ${\ell }_1,{\ell }_2$ and ${\ell }_{\infty }$ distances. All our algorithms run in $O(\log n)$ rounds of MPC for any fixed $d$ and achieve $(1+\epsilon )$-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.

Cited by in corpus (9)

• Connected Components at Scale via Local Contractions
• Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
• Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
• Near-Optimal Massively Parallel Graph Connectivity
• A Composable Coreset for k-Center in Doubling Metrics
• Exact Computation of a Manifold Metric, via Lipschitz Embeddings and Shortest Paths on a Graph
• New lower bounds for Massively Parallel Computation from query complexity
• On the Hardness of Massively Parallel Computation
• Symmetries: From Proofs To Algorithms And Back