2006 DictionaryofDistances

• (Deza & Deza, 2006) ⇒ Michel-Marie Deza, and Elena Deza. (2006). “Dictionary of Distances." Elsevier Science. ISBN:9780080465548

Subject Headings: Distance Function.

Notes

• Google Books Page: https://books.google.ca/books?id=I-PQH8gcOjUC

Cited By

• http://scholar.google.com/scholar?q=%222006%22+Dictionary+of+Distances

Quotes

Book Overview

Key features:

• Unicity: it is the first book treating the basic notion of Distance in whole generality.
• Interdisciplinarity: this Dictionaryis larger in scope than majority of thematic dictionaries.
• Encyclopedicity: while an Encyclopedia of Distances seems now too difficult to produce, this book (by its scope, short introductions and organization) provides the main material for it and for future tutorials on some parts of this material.
• Applicability: the distances, as well as distance-related notions and paradigms, are provided in ready-to-use fashion.
• Worthiness: the need and urgency for such dictionary was great in several huge areas, esp. Information Retrieval, Image Analysis, Speech Recognition and Biology.

Preface

The concept of distance is basic to human experience. In everyday life it usually means some degree of closeness of two physical objects or ideas, i.e., length, time interval, gap, rank difference, coolness or remoteness, while the term metric is often used as a standard for a measurement.

But here we consider, except for the last two chapters, the mathematical meaning of those terms, which is an abstraction of measurement.

The mathematical notions of distance metric (i.e., a function d (x, y) from X × X to the set of real numbers satisfying to d (x, y) = 0 with equality only for x = y, d (x, y) = d (y, x), and d (x, y) = d (x, z) +d (z, y)) and of metric space (X, d) were originated a century ago by M. Fréchet (1906) and F. Hausdor (1914) as a special case of an infinite topological space. The triangle inequality above appears already in Euclid. The infinite metric spaces are usually seen as a generalization of the metric|x - y|on the real numbers. Their main classes are the measurable spaces (add measure) and Banach spaces (add norm and completeness).

However, starting from K. Menger (who, in 1928, introduced metric spaces in Geometry) and L.M. Blumenthal (1953), an explosion of interest in both finite and infinite metric spaces occurred. Another trend is that many mathematical theories, in the process of their generalization, settled on the level of metric space. It is an ongoing process, for example, for Riemannian geometry, Real Analysis, Approximation Theory.

Distance metrics and distances have now become an essential tool in many areas of Mathematics and its applications including Geometry, Probability, Statistics, Coding / Graph Theory, Clustering, Data Analysis, Pattern Recognition, Networks, Engineering, Computer Graphics / Vision, Astronomy, Cosmology, Molecular Biology, and many other areas of science. Devising the most suitable distance metrics and similarities, to quantify the proximity between objects, has become a standard task for many researchers. Especially intense ongoing search for such distances occurs, for example, in Computational Biology, Image Analysis, Speech Recognition, and Information Retrieval.

Often the same distance metric appears independently in several different areas; for example, the edit distance between words, the evolutionary distance in Biology, the Levenstein distance in Coding Theory, and the Hamming + Gap or shuffle-Hamming distance.

This body of knowledge has become too big and disparate to operate in. The numbers of worldwide web entries offered by Google on the topics “distance,” “metric space” and “distance metric” approach 300 million (i.e., about 2% of all), 6.5 million and 5.5 million, respectively, not to mention all the printed information outside the Web, or the vast “invisible Web” of searchable databases. However, this vast information on distances is too scattered: the works evaluating distance from some list usually treat very specific areas and are hardly accessible to non-experts.

Therefore many researchers, including us, keep and cherish a collection of distances for use in their areas of science. In view of the growing general need for an accessible interdisciplinary source for a vast multitude of researchers, we have expanded our private collection into this Dictionary. Some additional material was reworked from various encyclopedias, especially Encyclopedia of Mathematics [ EM98], MathWorld [ Weis99], PlanetMath [ PM], and Wikipedia [ WFE ]. However, the majority of distances are extracted directly from specialist literature.

Besides distances themselves, we have collected many distance-related notions (especially in Chap. 1) and paradigms, enabling people from applications to get those (arcane for non-specialists) research tools, in ready-to-use fashion. This and the appearance of some distances in di ? erent contexts can be a source of new research.

In the time when over-specialization and terminology fences isolate researchers, this Dictionary tries to be “centripetal” and “ecumenical,” providing some access and altitude of vision but without taking the route of scienti ? c vulgarization. This attempted balance has de ? ned the structure and style of the Dictionary.

This reference book is a specialized encyclopedic dictionary organized by subject area. It is divided into 29 chapters grouped into seven parts of about the same length. The titles of the parts are purposely approximative: they allow a reader to ? gure out her / his area of interest and competence. For example, Parts II, III and IV, V require some culture in, respectively, pure and applied Mathematics. Part VII can be read by a layman.

The chapters are thematic lists, by areas of Mathematics or applications, which can be read independently. When necessary, a chapter or a section starts with a short introduction: a ? eld trip with the main concepts. Besides these introductions, the main properties and uses of distances are given, within items, in some instances. We also tried, when it was easy, to trace distances to their originator (s), but the proposed extensive bibliography has a less general ambition: just to provide convenient sources for a quick search.

Each chapter consists of items ordered in a way that hints of connections between them. All item titles and (with majiscules only for proper nouns) selected key terms can be traced in the large Subject Index; they are boldfaced unless the meaning is clear from the context. So, the de ? nitions are easy to locate, by subject, in chapters and/or, by alphabetic order, in the Subject Index.

The introductions and de ? nitions are reader-friendly and generally independent of each other; but they are interconnected, in the three-dimensional HTML manner, by hyperlink-like boldfaced references to similar de ? nitions.

Many nice curiosities appear in this “Who is Who” of distances. Examples of such sundry terms are: ubiquitous Euclidean distance (“as-the-crow - ? ies”), ? ower-shop metric (shortest way between two points, visiting a “? ower-shop” point ? rst), knight-move metric on a chessboard, Gordian distance of knots, Earth Mover distance, biotope distance, Procrustes distance, lift metric, Post O ? ce metric, Internet hop metric, WWW hyperlink quasi-metric, Moscow metric, and dogkeeper distance.

Besides abstract distances, the distances having physical meaning also appear (especially in Part VI); they range from 1.6 × 10-35 m (Planck length) to 4.3 × 1026 m (the estimated size of the observable Universe, about 27 × 1060 Planck lengths).

The number of distance metrics is infinite, and therefore our Dictionary cannot enumerate all of them. But we were inspired by several successful thematic dictionaries on other infinite lists; for example, on Numbers, Integer Sequences, Inequalities, Random Processes, and by atlases of Functions, Groups, Fullerenes, etc. On the other hand, the large scope often forced us to switch to the mode of laconic tutorial.

The target audience consists of all researchers working on some measuring schemes and, to a certain degree, students and a part of the general public interested in science.

We have tried to address, even if incompletely, all scienti ? c uses of the notion of distance. But some distances did not made it to this Dictionary due to space limitations (being too speci ? c and/or complex) or our oversight. In general, the size / interdisciplinarity cut-o ?, i.e., decision where to stop, was our main headache. We would be grateful to readers who send us their favorite distances missed here. Four pages at the end are reserved for such personal additions.

5. Metrics on Normed Structures

...

• Group norm metrics
  A group norm metrics is a metric on a group ([math]\displaystyle{ G, +, 0 }[/math]), defined by :[math]\displaystyle{ \mid\mid x + (-y)\mid\mid= \mid\mid x - y \mid\mid }[/math], where [math]\displaystyle{ \mid\mid . \mid\mid }[/math] is a group norm on G, i.e., a function [math]\displaystyle{ \mid\mid . \mid\mid: G \rightarrow \mathbb{R} }[/math] such that, for all [math]\displaystyle{ x, y \in G }[/math] we have the following properties
• Any group norm metric d is right-invariant, i.e., …

…

10. Distances in Algebra

...

• Order Norm Metric: … The order norm metric is a group norm metric on G, defined by : [math]\displaystyle{ \mid\mid x \cdot y^{-1}\mid\mid_{ord'} }[/math].

…

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2006 DictionaryofDistances	Michel-Marie Deza Elena Deza			Dictionary of Distances						2006