Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

Abstract

We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set X ⊂ ℝd of n points, the goal is to produce a spanning tree for X with weight within a small factor of optimal. Euclidean MST is one of the most fundamental hierarchical geometric clustering algorithms, and with the proliferation of enormous high-dimensional data sets, such as massive transformer-based embeddings, there is now a critical demand for efficient distributed algorithms to cluster such data sets.

Locations

• arXiv (Cornell University) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View