Fast, Linear Time Hierarchical Clustering using the Baire Metric

Pedro Contreras, Fionn Murtagh

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


The Baire metric induces an ultrametric on a dataset and is of linear computational complexity, contrasted with the standard quadratic time agglomerative hierarchical clustering algorithm. In this work we evaluate empirically this new approach to hierarchical clustering. We compare hierarchical clustering based on the Baire metric with (i) agglomerative hierarchical clustering, in terms of algorithm properties; (ii) generalized ultrametrics, in terms of definition; and (iii) fast clustering through k-means partitioning, in terms of quality of results. For the latter, we carry out an in depth astronomical study. We apply the Baire distance to spectrometric and photometric redshifts from the Sloan Digital Sky Survey using, in this work, about half a million astronomical objects. We want to know how well the (more costly to determine) spectrometric redshifts can predict the (more easily obtained) photometric redshifts, i. e. we seek to regress the spectrometric on the photometric redshifts, and we use clusterwise regression for this.

Original languageEnglish
Pages (from-to)118-143
Number of pages26
JournalJournal of Classification
Issue number2
Publication statusPublished - 1 Jul 2012
Externally publishedYes


Dive into the research topics of 'Fast, Linear Time Hierarchical Clustering using the Baire Metric'. Together they form a unique fingerprint.

Cite this