# Natural Hierarchical Cluster Analysis by Nearest Neighbors with Near-Linear Time Complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 53 references that are in the map.
- First posted on arXiv 15 Mar 2022.

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

- [Online Clustering of Bandits](https://mlsanity.com/paper/1401.8257/) (2014)
- [Sequential Outlier Detection based on Incremental Decision Trees](https://mlsanity.com/paper/1803.03674/) (2018)
- [Optimal Exploitation of Clustering and History Information in Multi-Armed Bandit](https://mlsanity.com/paper/1906.03979/) (2019)
- [Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering](https://mlsanity.com/paper/2109.02082/) (2021)
- [Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1911.11122/) (2019)
- [Graph Signal Processing -- Part I: Graphs, Graph Spectra, and Spectral Clustering](https://mlsanity.com/paper/1907.03467/) (2019)
- [A True O(n logn)  Algorithm for the All-k-Nearest-Neighbors Problem](https://mlsanity.com/paper/1908.00159/) (2019)

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

- [Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design](https://mlsanity.com/paper/2203.12011/) (2022)

## Abstract (arXiv)

We propose a nearest neighbor based clustering algorithm that results in a naturally defined hierarchy of clusters. In contrast to the agglomerative and divisive hierarchical clustering algorithms, our approach is not dependent on the iterative working of the algorithm, in the sense that the partitions of the hierarchical clusters are purely defined in accordance with the input dataset. Our method is a universal hierarchical clustering approach since it can be implemented as bottom up or top down versions, both of which result in the same clustering. We show that for certain types of datasets, our algorithm has near-linear time and space complexity.