Reference: Distance Metrics

Each metric above can be written as a function $d: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}_{\geq 0}$ satisfying (for true metrics) the four axioms:

1. Non-negativity: $d(x, y) \geq 0$
2. Identity: $d(x, y) = 0 \iff x = y$
3. Symmetry: $d(x, y) = d(y, x)$
4. Triangle inequality: $d(x, z) \leq d(x, y) + d(y, z)$

Most of the roster above satisfies all four; cosine distance ($1 - \cos\theta$) satisfies (1), (2), (3) but violates the triangle inequality in general — it is a pseudometric on the unit sphere and a divergence off it. Jaccard distance is a true metric on sets. Hamming is a true metric on equal-length binary strings.

Minkowski family

$d_p(x, y) = \left( \sum_{i=1}^{n} |x_i - y_i|^p \right)^{1/p}, \quad p \geq 1$

Special cases:

• $p = 1$: Manhattan (cityblock)
• $p = 2$: Euclidean (the default euclidean)
• $p \to \infty$: Chebyshev (chebyshev = np.max(np.abs(x - y)))

For $p < 1$ the Minkowski formula is not a metric (triangle inequality fails) — but the fractional Lp distances with $0 < p < 1$ are sometimes used in high-dimensional settings to counteract the curse of dimensionality (see Aggarwal, Hinneburg & Keim 2001).

Cosine

$d_{\cos}(x, y) = 1 - \cos\theta = 1 - \frac{x \cdot y}{\lVert x \rVert \, \lVert y \rVert} = 1 - \frac{\sum_i x_i y_i}{\sqrt{\sum_i x_i^2} \sqrt{\sum_i y_i^2}}$

When $x$ and $y$ are both unit-norm, $d_{\cos}(x, y) = 1 - x \cdot y$, and cosine distance and Euclidean distance give the same ranking because $\lVert x - y \rVert^2 = 2(1 - x \cdot y)$ for unit vectors.

Jaccard

$d_J(A, B) = 1 - \frac{|A \cap B|}{|A \cup B|}$

For multiset / count vectors, the generalized Jaccard (Tanimoto coefficient) replaces the set cardinalities with $\frac{\sum_i \min(x_i, y_i)}{\sum_i \max(x_i, y_i)}$.

Mahalanobis

$d_M(x, y) = \sqrt{(x - y)^\top \Sigma^{-1} (x - y)}$

Geometrically, Mahalanobis is Euclidean distance applied after whitening the data: if $\Sigma = U \Lambda U^\top$ is the eigendecomposition, then $\Sigma^{-1} = U \Lambda^{-1} U^\top$, and the transform $z = \Lambda^{-1/2} U^\top (x - y)$ rescales each principal axis by $1/\sqrt{\lambda_i}$. The result is a vector whose components are uncorrelated and unit-variance, and the Euclidean norm of $z$ equals $d_M(x, y)$.

A concrete worked value for the toy example in the code block: with $\Delta = (-2, 2, 0, 4)$ and

$\Sigma^{-1} \approx \begin{pmatrix} 0.5714 & -0.2857 & 0 & 0 \\ -0.2857 & 1.1429 & 0 & 0 \\ 0 & 0 & 2.0 & 0 \\ 0 & 0 & 0 & 0.3333 \end{pmatrix}$

we have

$d_M^2 = \Delta^\top \Sigma^{-1} \Delta \approx 14.476, \qquad d_M \approx 3.805.$

The full expansion splits into the coupled axis-0/axis-1 block ($\approx 9.143$ — the off-diagonal $0.5$ entries in $\Sigma$ mean the inversion mixes those two axes, so the contribution of axis 0 is not simply $\Delta_0^2 / \Sigma_{00}$), plus the independent axis-2 term ($0^2 \times 2.0 = 0$), plus the independent axis-3 term ($4^2 \times 0.3333 \approx 5.333$).

Curse of dimensionality sidebar

As the number of dimensions $n$ grows, all of the Minkowski-family distances converge on the same value for any pair of points drawn from the same distribution. The intuition:

• The expected squared Euclidean distance between two i.i.d. points in $n$ dimensions grows as $\Theta(n)$.
• The variance of that distance also grows as $\Theta(n)$.
• But the relative spread $\frac{\text{std}(d)}{\mathbb{E}[d]}$ shrinks as $\Theta(1/\sqrt{n})$.

So in very high dimensions, every pair of points is (in a normalized sense) about equally far from every other pair — the nearest neighbour and the farthest neighbour become nearly indistinguishable. KNN, hierarchical clustering, and most density-based methods become unreliable.

Mitigations:

1. Reduce dimensionality first: PCA, UMAP, or autoencoders down to a few dozen dims before computing distances.
2. Use cosine for sparse high-dimensional text: it normalizes out the magnitude that grows with $n$.
3. Use fractional Lp with $p < 1$ (Aggarwal, Hinneburg & Keim 2001): the smaller $p$, the more weight is given to close axes rather than far axes, partially counteracting the concentration effect.
4. Use feature selection to drop irrelevant dimensions — a noisy feature in high-dim data is worse than no feature at all, because it adds distance without adding signal.
5. Accept it: some methods (random forests, gradient-boosted trees, linear models with regularization) do not depend on distances at all and bypass the issue entirely.

For a deeper treatment, see the KNN/curse-of-dimensionality article in the corpus.

Edge cases + common mistakes

Scale, magnitude, and covariance issues

1. Euclidean on un-scaled features. If feature A ranges over $[0, 1]$ and feature B over $[0, 1000]$, Euclidean distance is dominated by B. Standardize (z-score) or min-max scale before computing distances. Or use Mahalanobis, which scales each axis by its variance automatically.

2. Cosine on zero vectors. Cosine is undefined when either vector has zero norm — the denominator is zero. Libraries return nan or raise; in pipelines, filter zero rows first or add a tiny epsilon.

3. Mahalanobis with a singular covariance. If you have more features than samples, or perfectly correlated features, $\Sigma$ is singular and $\Sigma^{-1}$ does not exist. Use the pseudo-inverse (np.linalg.pinv) or regularize: $\Sigma_{\text{reg}} = \Sigma + \epsilon I$ for small $\epsilon$.

4. Mahalanobis with a stale covariance. $\Sigma$ must be estimated from a representative sample of your data. If you estimate it on a training set that has different scaling or correlation structure than the points you later measure, the distances are meaningless. Re-estimate when the data distribution drifts.

Set, string, and exponent edge cases

5. Jaccard on multisets. Vanilla Jaccard treats inputs as sets — duplicates are lost. If you have count vectors (e.g., a bag of words with weights), use the generalized Tanimoto coefficient $\sum \min(x_i, y_i) / \sum \max(x_i, y_i)$ instead.

6. Hamming on unequal-length strings. Hamming requires inputs of equal length. For variable-length strings, use Levenshtein (edit distance), which is the minimum number of single-character edits (insertions, deletions, substitutions) needed to turn one string into another.

7. Minkowski with $p < 1$. It is not a true metric (triangle inequality fails). It is sometimes useful in high-dim settings per Aggarwal et al., but do not pass it to a KNN implementation that assumes a true metric — the result may not even satisfy the triangle inequality, breaking neighbour-search optimizations like ball trees.

Conventions and comparability

8. Cosine distance vs. cosine similarity. Many libraries (scipy, sklearn) return 1 - cos as “cosine distance” — that is a distance-like quantity (smaller = more similar). Other libraries (pytorch, some transformers) return the raw cos as “cosine similarity” (larger = more similar). Mixing the two conventions silently flips your ranking. Always check the sign and the range before plugging a cosine into a downstream metric.

9. Treating cosine as a true metric. Cosine distance does not satisfy the triangle inequality in general. It is fine for similarity search and for KNN-style retrieval (where you only care about top-k ranking, not metric properties), but it is not safe for methods that assume a metric — e.g., metric multidimensional scaling, ball-tree indexing with a metric assumption, or any algorithm that relies on the triangle inequality to prune candidates.

10. Using the metric the library defaults to. sklearn’s KNeighborsClassifier defaults to p=2 (Euclidean). That is a reasonable default for low-dim isotropic data, but it is not a universal best choice. Always pick the metric to match the data geometry, not the library default.

11. Comparing distances across metrics. A Euclidean distance of 4.899 and a Manhattan distance of 8.0 between the same pair are not “the same distance” in different units — they are different functions that happen to share the word “distance” in their name. Only compare rankings produced by the same metric across different candidate points, never the raw values of different metrics to each other.

Cross-references

• Why your KNN model fails in high dimensions) — the curse-of-dimensionality article this reference cross-links into; explains in depth why Minkowski distances concentrate as $n \to \infty$ and what to do about it.
• Vector databases compared) — covers cosine vs. Euclidean for ANN (approximate nearest neighbour) indexing, including the HNSW / IVF / PQ trade-offs that depend on the distance metric.
• Building your first RAG pipeline) — uses cosine similarity over OpenAI or SBERT embeddings as the retrieval step; the choice of cosine (over Euclidean) is justified by the unit-norm normalization that most embedding providers apply.
• SHAP values — uses a distance-weighted kernel (a variant of Mahalanobis-like weighting) to approximate local model behaviour around a single prediction; the choice of kernel bandwidth is essentially a choice of distance scale.

Further reading

• Deza, M.M. & Deza, E. (2009). Encyclopedia of Distances. Springer. The comprehensive reference: every named distance metric in the literature, organized by family. Use as a dictionary, not as a textbook.
• Aggarwal, C.C., Hinneburg, A. & Keim, D.A. (2001). On the Surprising Behavior of Distance Metrics in High Dimensional Space. ICDT 2001. The foundational paper on the curse of dimensionality for distance metrics; motivates the use of fractional $L_p$ norms with $p < 1$ in high-dim data.
• Cosine similarity and the triangle inequality — NIST/AMS technical discussions on the metric properties of cosine; useful when deciding whether cosine is safe for your specific algorithm.
• scipy.spatial.distance — the canonical Python reference for the metrics above; docs include the exact formulas and edge-case behaviour.
• sklearn.neighbors — KNN implementations supporting Minkowski with arbitrary $p$; useful for experimenting with the impact of $p$ on neighbour selection.

For a Kaggle competition where the choice of distance metric materially affects results, see the Spotify Million Playlist Dataset recommender-style exercises: cosine over track-count vectors consistently outperforms Euclidean there because the data is sparse and high-dimensional.