On ultrametricity, data coding, and computation

Research output: Contribution to journalArticle

60 Citations (Scopus)

Abstract

The triangular inequality is a defining property of a metric space, while the stronger ultrametric inequality is a defining property of an ultrametric space. Ultrametric distance is defined from p-adic valuation. It is known that ultrametricity is a natural property of spaces in the sparse limit. The implications of this are discussed in this article. Experimental results are presented which quantify how ultrametric a given metric space is. We explore the practical meaningfulness of this property of a space being ultrametric. In particular, we examine the computational implications of widely prevalent and perhaps ubiquitous ultrametricity.

Original languageEnglish
Pages (from-to)167-184
Number of pages18
JournalJournal of Classification
Volume21
Issue number2
DOIs
Publication statusPublished - 1 Sep 2004
Externally publishedYes

    Fingerprint

Cite this