# Hierarchical Clustering for Euclidean Data

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2018.

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

- [Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs](https://mlsanity.com/paper/2112.09055/) (2021)
- [Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost](https://mlsanity.com/paper/2205.14198/) (2022)
- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [On the cohesion and separability of average-link for hierarchical agglomerative clustering](https://mlsanity.com/paper/2411.05097/) (2024)
- [Hierarchical Clustering: New Bounds and Objective](https://mlsanity.com/paper/2111.06863/) (2021)

## Abstract (arXiv)

Recent works on Hierarchical Clustering (HC), a well-studied problem in exploratory data analysis, have focused on optimizing various objective functions for this problem under arbitrary similarity measures. In this paper we take the first step and give novel scalable algorithms for this problem tailored to Euclidean data in R^d and under vector-based similarity measures, a prevalent model in several typical machine learning applications. We focus primarily on the popular Gaussian kernel and other related measures, presenting our results through the lens of the objective introduced recently by Moseley and Wang [2017]. We show that the approximation factor in Moseley and Wang [2017] can be improved for Euclidean data. We further demonstrate both theoretically and experimentally that our algorithms scale to very high dimension d, while outperforming average-linkage and showing competitive results against other less scalable approaches.