Large-Scale Euclidean MST and Hierarchical Clustering

We present new fast algorithms for performing the single-linkage hierarchical clustering method, a classical data mining method used heavily in bioinformatics and astronomy, given similarities which are metrics. We present experimental results that demonstrate significant speedup over previous algorithms on both synthetic and real data, including a dataset of 3 million astronomical observations and a dataset of protein folding trajectories. Additionally, our algorithms use considerably less storage than previous methods. More generally, our algorithm appears to be the fastest practical solution to the well-known Euclidean Minimum Spanning Tree problem.