On ultrametricity, data coding, and computation

Research output: Contribution to journalArticle

57 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

coding
Coding
Ultrametric Space
Metric space
P-adic
Valuation
Triangular
Quantify
Experimental Results

Cite this

@article{3c0d0d6286d54d7b846d42631f71af2c,
title = "On ultrametricity, data coding, and computation",
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.",
keywords = "Binary tree, Classification, Clustering, Dendrogram, Hierarchy, Isosceles, Metric, Non-Archimedean, p-Adic, Ultrametric, Unsupervised",
author = "Fionn Murtagh",
year = "2004",
month = "9",
day = "1",
doi = "10.1007/s00357-004-0015-y",
language = "English",
volume = "21",
pages = "167--184",
journal = "Journal of Classification",
issn = "0176-4268",
publisher = "Springer New York",
number = "2",

}

On ultrametricity, data coding, and computation. / Murtagh, Fionn.

In: Journal of Classification, Vol. 21, No. 2, 01.09.2004, p. 167-184.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On ultrametricity, data coding, and computation

AU - Murtagh, Fionn

PY - 2004/9/1

Y1 - 2004/9/1

N2 - 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.

AB - 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.

KW - Binary tree

KW - Classification

KW - Clustering

KW - Dendrogram

KW - Hierarchy

KW - Isosceles

KW - Metric

KW - Non-Archimedean

KW - p-Adic

KW - Ultrametric

KW - Unsupervised

UR - http://www.scopus.com/inward/record.url?scp=17544364135&partnerID=8YFLogxK

U2 - 10.1007/s00357-004-0015-y

DO - 10.1007/s00357-004-0015-y

M3 - Article

VL - 21

SP - 167

EP - 184

JO - Journal of Classification

JF - Journal of Classification

SN - 0176-4268

IS - 2

ER -