Massively Parallel Tree Embeddings for High Dimensional Spaces

Abstract

Efficient computation on massive high-dimensional data greatly benefits from efficient embedding techniques into simpler metrics. Perhaps the most celebrated technique is the dimension reduction à-la Johnson and Lindenstrauss [46]. Another important method embeds the data into a tree metric space, first efficiently achieved by Bartal [14]. Both of these algorithmic tools are among the most general theorems with numerous applications. In this paper, we study these two embedding methods in the Massively Parallel Computation (MPC) model. We develop a new hybrid partitioning algorithm which generalizes both random shifted grid and ball partitioning methods for generating tree embeddings. This leads to an 𝑂(1)-round randomized MPC algorithm for embedding high-dimensional data into a tree while approximating the distance between any two points within a factor of 𝑂e(log1.5 𝑛) (and thus distortion 𝑂e(log1.5 𝑛)) in expectation as long as the aspect ratio is 𝑂(poly(𝑛)). This Euclidean result beats the lower bound of Ω(log𝑛) MPC rounds for tree embeddings of general metric spaces and can extend to a number of problems, including densest ball, minimum spanning tree, and Earth-Mover distance. Along the way, we implement and use Ailon and Chazelle’s Fast Johnson Lindenstrauss Transform [2] with sublinear memory and 𝑂(1) MPC rounds, which is of its own interest.