# Modern hierarchical, agglomerative clustering algorithms

Source: [Modern hierarchical, agglomerative clustering algorithms](<https://www.sota2.com/research/paper/68fa60591e209131ce9ef091>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T19:38:40.516Z

Authors: Daniel M\\"ullner

Published: 2011-09-12T05:49:11.000Z

## Abstract

This paper presents algorithms for hierarchical, agglomerative clustering which perform most efficiently in the general-purpose setup that is given in modern standard software. Requirements are: (1) the input data is given by pairwise dissimilarities between data points, but extensions to vector data are also discussed (2) the output is a "stepwise dendrogram", a data structure which is shared by all implementations in current standard software. We present algorithms (old and new) which perform clustering in this setting efficiently, both in an asymptotic worst-case analysis and from a practical point of view. The main contributions of this paper are: (1) We present a new algorithm which is suitable for any distance update scheme and performs significantly better than the existing algorithms. (2) We prove the correctness of two algorithms by Rohlf and Murtagh, which is necessary in each case for different reasons. (3) We give well-founded recommendations for the best current algorithms for the various agglomerative clustering schemes.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Hierarchical Generative Modeling on 20 Newsgroups text](<https://www.sota2.com/research/sota/hierarchical-generative-modeling-on-20-newsgroups-text.md>): Hierarchical Generative Modeling; 20 Newsgroups text; DP: 13.1.

- [Hierarchical Generative Modeling on Fashion-Mnist](<https://www.sota2.com/research/sota/hierarchical-generative-modeling-on-fashion-mnist.md>): Hierarchical Generative Modeling; Fashion MNIST; DP: 45.

- [Hierarchical Generative Modeling on MNIST](<https://www.sota2.com/research/sota/hierarchical-generative-modeling-on-mnist.md>): Hierarchical Generative Modeling; MNIST; DP: 63.7.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1109.2378>)

[PDF](<https://arxiv.org/pdf/1109.2378.pdf>)
