Clustering in Very High Dimensions

Fionn Murtagh

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the 2005 UK Workshop on Computational Intelligence
Subtitle of host publicationUKCI 2005
EditorsBoris Mirkin, George Magoulas
PublisherBirkbeck, University of London
Number of pages6
Publication statusPublished - 2005
Externally publishedYes
EventUK Workshop on Computational Intelligence - Birkbeck, University of London, London, United Kingdom
Duration: 5 Sep 20057 Sep 2005


ConferenceUK Workshop on Computational Intelligence
Abbreviated titleUKCI 2005
Country/TerritoryUnited Kingdom
Internet address


Dive into the research topics of 'Clustering in Very High Dimensions'. Together they form a unique fingerprint.

Cite this