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
partititioning, in terms of quality of results.

Data analysis and data mining are concerned with unsupervised pattern finding
and structure determination in data sets. "Structure" can be understood as
symmetry and a range of symmetries are expressed by hierarchy. Such symmetries
directly point to invariants, that pinpoint intrinsic properties of the data
and of the background empirical domain of interest. We review many aspects of
hierarchy here, including ultrametric topology, generalized ultrametric,
linkages with lattices and other discrete algebraic structures and with p-adic
number representations.