2018
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering under $\ell_p$ Distances
ICML 2018oral
We present first 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 achiev…