Clustering in Very High Dimensions

High dimensional data typify pattern recognition problems in bioinformatics, information retrieval, and various other fields. We discuss metric space properties in the context of four scenarios: increased dimensionality leading to larger
dissimilarities; uniform and Gaussian distributed points in the context of increasing dimensionality; and how pivot-based search can be understood in high dimensions. Conclusions include: (i) preprocessing using an ultrametric data structure (i.e., resulting from a hierarchical clustering) can lead to far faster proximity searching, among other operations; (ii) a locally ultrametric topology is targeted by pivot-based branch and bound searching; but (iii) high dimensional, structureless data (e.g., uniformly or Gaussian distributed) also become ultrametric.