Distance Metric

(Redirected from Distance Function)

A distance metric is a symmetric metric that maps two items, $\displaystyle{ x,y }$, to a non-negative distance value where $\displaystyle{ \text{Dist}(x,x)=\text{Dist}(y,y)=0 }$ and is also constrained the triangle inequality.

References

2010

• (Wikipedia, 2010) http://en.wikipedia.org/wiki/Metric_(mathematics)
• In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space.
• A metric on a set X is a function (called the distance function or simply distance) d : X × X → R (where R is the set of real numbers).
• For all x, y, z in X, this function is required to satisfy the following conditions:
• 1. d(x, y) ≥ 0 (non-negativity)
• 2. d(x, y) = 0 if and only if x = y (identity of indiscernibles. Note that condition 1 and 2 together produce positive definiteness)
• 3. d(x, y) = d(y, x) (symmetry)
• 4. d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
• These axioms are not independent: Non-negativity follows from the other axioms.
• A metric is called an ultrametric if it satisfies the following stronger version of the triangle inequality:
• For all x, y, z in M, d(x, z) ≤ max(d(x, y), d(y, z))
• A metric d on X is called intrinsic if any two points x and y in X can be joined by a curve with length arbitrarily close to d(x, y).

2001

• (Ramon & Bruynooghe, 2001) ⇒ Jan Ramon, and M. Bruynooghe. (2001). “A polynomial time computable metric between point sets.” In: Acta Inform. 37, 765–780.

1998

• (Bunke & Shearer, 1998) ⇒ Horst Bunke, and Kim Shearer. (1998). “A graph distance metric based on the maximal common subgraph.” In: Pattern Recognition Lett. 19, 255–259.
• (Ramon et al., 1998) ⇒ Jan Ramon, M. Bruynooghe, and W. Van Laer. (1998). “Distance Measures Between Atoms.” In: ProceedingsCompulogNet Area Meeting on ’Computational Logic and Machine Learning’, pp. 35–41.

1979

• (Tai, 1979) ⇒ K. Tai. (1979). “Tree to Tree Correction Problem.” In: ACM 26 (3), 422–433.