Approximate Single Linkage Cluster Analysis of Large Data Sets in High Dimensional Spaces

William F. Eddy, Audris Mockus, and Shingo Oue


Motivated by a real-world data set of more than 40,000 observations, we consider single linkage clustering of large data sets in high dimensional spaces. In this particular case, the data we consider are observations in the space of one dimensional sub-manifolds of Euclidean space. This data set is so large that the individual observations cannot each be inspected. A goal of the analysis is to produce a partial ordering of the data so that a useful inspection of selected observations can take place. An essential step is construction of a metric on the objects in this high dimensional space that can be computed fairly quickly. The size of the problem makes the running time of Prim's algorithm (the fastest available algorithm for finding a minimal spanning tree of a complete graph) prohibitive. We have developed several methods which approximate the single linkage tree. We report the result of applying our approximations to the data set.

Here is the full postscript text for this technical report. It is 3.648 Mbytes (thats MegaBytes).