Distance Metric

(Redirected from Similarity Metric)
Jump to navigation Jump to search

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



  • (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).







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


  • (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.



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