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

arXiv: https://arxiv.org/abs/2104.01126 · HTML: https://mlsanity.com/paper/2104.01126/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 60 references that are in the map.
- First posted on arXiv 2 Apr 2021.

## Builds on (most cited first, 2 of 2)

- [Theoretically-Efficient and Practical Parallel DBSCAN](https://mlsanity.com/paper/1912.06255/) (2019)
- [Faster DB-scan and HDB-scan in Low-Dimensional Euclidean Spaces](https://mlsanity.com/paper/1702.08607/) (2017)

## Built on by (most cited first, 9 of 9)

- [ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain](https://mlsanity.com/paper/2106.04727/) (2021)
- [NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems](https://mlsanity.com/paper/2210.12453/) (2022)
- [Geometric reconstructions of density based clusterings](https://mlsanity.com/paper/2203.08020/) (2022)
- [PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU](https://mlsanity.com/paper/2401.06089/) (2024)
- [Sparsification and Reconstruction from the Perspective of Representation Geometry](https://mlsanity.com/paper/2505.22506/) (2025)
- [FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data](https://mlsanity.com/paper/2507.14261/) (2025)
- [Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering](https://mlsanity.com/paper/2509.06214/) (2025)
- [Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion](https://mlsanity.com/paper/2602.24232/) (2026)
- [Lumbermark: Resistant Clustering by Chopping Up Mutual Reachability Minimum Spanning Trees](https://mlsanity.com/paper/2604.07143/) (2026)

## Abstract (arXiv)

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 present a parallel approximate algorithm for OPTICS based on a recent sequential algorithm by Gan and Tao. Finally, we 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). We implement our algorithms and propose a memory optimization that requires only a subset of well-separated pairs to be computed and materialized, leading to savings in both space (up to 10x) and time (up to 8x). Our experiments on large real-world and synthetic data sets using a 48-core machine show that our fastest algorithms outperform the best serial algorithms for the problems by 11.13--55.89x, and existing parallel algorithms by at least an order of magnitude.