Mathematics

Computer science

Computation

Parallel algorithm

Matching (statistics)

Divide and conquer algorithms

Algorithm

Euclidean minimum spanning tree

Kruskal's algorithm

Cluster analysis

Tree (set theory)

Combinatorics

Euclidean space

Distributed minimum spanning tree

Artificial intelligence

Statistics

Minimum spanning tree

Spanning tree

Reachability

This paper presents new parallel algorithms for generating Euclidean minimum spanning trees and spatial clustering hierarchies (known as HDBSCAN*). Our approach is based on generating a well-separated pair decomposition followed by using Kruskal's minimum spanning tree algorithm and bichromatic closest pair computations. We introduce a new notion of well-separation to reduce the work and space of our algorithm for HDBSCAN*. We also give a new parallel divide-and-conquer algorithm for computing the dendrogram and reachability plots, which are used in visualizing clusters of different scale that arise for both EMST and HDBSCAN*. We show that our algorithms are theoretically efficient: they have work (number of operations) matching their sequential counterparts, and polylogarithmic depth (parallel time).

Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering