Metric measure

The fact that a measure is a metric allows optimizations in many applications. For example, many efficient algorithms for searching shortest paths in graphs, such as Dijkstra’s algorithm, make use of the fact that the underlying measure is a metric.

$d: U \times U \rightarrow R^+ \cup \{0\}$ is called metric if the following holds:

• $d(x,y) \geq 0$ non-negativity
• $d(x,y) = d(y,x)$ symmetry
• $x = y \Leftrightarrow d(x,y) = 0$ identity
• $d(x,z) \leq d(x,y) + d(y,z)$ triangle inequality

Metric measure sometimes called (mathematical) distance. But not every string measure which is historically called “distance” is a metric, so it’s better to use word metric to avoid confusion.

Minkowski distance

Minkowski distance is an example of metric measure (not typically used as string measure though, given here as an example)

$$D\left(X,Y\right) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{\frac{1}{p}}$$

where $X = (x_1,x_2,\ldots,x_n) \text{ and } Y = (y_1,y_2,\ldots,y_n) \in R^n$. For $p \geq 1$ , the Minkowski distance is a metric.

• $p = 1$ Manhattan distance
• $p = 2$ Euclidean distance
• $p \rightarrow \infty$ Chebyshev distance