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

2017/10/04 by Yaroslavtsev, Grigory, Vadapalli, Adithya
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1710.01431

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, ℓ₁, ℓ₂ 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.

Related

• Fully Scalable MPC Algorithms for Clustering in High Dimension
• It's Hard to HAC with Average Linkage!
• Almost 3-Approximate Correlation Clustering in Constant Rounds
• On Randomly Projected Hierarchical Clustering with Guarantees
• Parallel Hierarchical Agglomerative Clustering in Low Dimensions