Distance, Scaling, and the Curse of Dimensionality

A metric returns a number. Almost any pair of encoded rows will produce one. That number is useful only when feature differences correspond to meaningful similarity.

No metric is universally neutral, and the claim has been tested rather than asserted.

The exponent in the L_k norm is a choice, and it changes what the distance means. A 2001 paper by Aggarwal and two colleagues examined exactly that. They found “that the problem of meaningfulness in high dimensionality is sensitive to the value of k”, and drew a recommendation from it: “the Manhattan distance metric (L1 norm) is consistently more preferable than the Euclidean distance metric (L2 norm) for high dimensional data mining applications”. Pushing k below 1 helped further. Those fractional distance metrics are no longer metrics in the strict sense, and the paper reports that they “can significantly improve the effectiveness of standard clustering algorithms such as the k-means algorithm”.

The size of that improvement sits in their k-means experiment: six clusters of 10,000 points each, at d = 20. “The results of our experiments show that the fractional distance metrics provides a much higher classification rate which is about 99% for the fractional distance metric with f = 0.3 versus 89% for the Euclidean metric”. A different exponent, and nothing else, moved the classification rate from 89% to about 99%.

Two later groups then tested the recommendation and did not confirm it as a general rule. François and colleagues at the Université catholique de Louvain proved in 2007 that “fractional norms are not always less concentrated than higher order norms”. Mirkes and two colleagues ran the comparison again in 2020, in a paper whose title says that fractional norms and quasinorms do not help to overcome the curse of dimensionality. They found that “the difference of the performance of kNN based on lp for p=2, 1, and 0.5 is statistically insignificant”. Euclidean distance is a default rather than a neutral choice. L1 is a hypothesis to test on your own data, not a repair to adopt on someone else's synthetic workload.

How much the choice can be worth is visible on a fixed benchmark. MNIST is 60,000 training and 10,000 test images. Hold the classifier family at k-nearest-neighbour and change only the distance. The benchmark table published by Yann LeCun and Corinna Cortes lists Euclidean L2 at 5.0% test error for LeCun et al. 1998. On identical unprocessed data it lists L2 at 3.09% against L3 at 2.83% (Kenneth Wilder). Tangent distance reaches 1.1%. The image distortion model reaches 0.54%, and its P2DHMDM variant 0.52%. From 5.0% to 0.52% is roughly a factor of ten, moved by the distance function alone.

Read the column carefully, though. The pixels are not held constant all the way down it. Only the 3.09%-versus-2.83% pair is a strictly like-for-like swap on unprocessed data. The lowest rows are matching procedures rather than formulas. Keysers describes his this way: “The distance as determined by the best match between two images is then used within a 3-nearest-neighbor classifier.”

Euclidean, Manhattan, cosine and Mahalanobis are four points in that space of choices: straight-line distance after encoding and scaling; coordinate-wise absolute difference; angle rather than magnitude; and covariance-adjusted distance that needs a stable covariance estimate and a reference distribution to be adjusted against.

As irrelevant dimensions accumulate, distances often become less discriminative.

Add enough dimensions and the nearest point stops being different from the farthest one. Beyer and three colleagues at the University of Wisconsin–Madison proved that in 1999, and then measured where it bites. Their abstract states the result: “We show that under a broad set of conditions (much broader than independent and identically distributed dimensions), as dimensionality increases, the distance to the nearest data point approaches the distance to the farthest data point.” The practical number is smaller than people expect. The effect “can occur for as few as 10-15 dimensions”, and in their synthetic experiments the distinction blurs at 15. On the workloads they examined, “linear scan would outperform the techniques being proposed on the workloads studied in high (10-15) dimensionality”. They are careful about the boundary of the claim. They also “identify special workloads for which the concept of nearest neighbor continues to be meaningful in high dimensionality”.

The result did not stay one paper's claim. François and colleagues re-derived it independently in 2007 and established that the concentration “is indeed an intrinsic property of the distances and not an artifact from a finite sample”. It tracks intrinsic dimension rather than embedding dimension. A column count is therefore not by itself a diagnosis.

Flattened distances are only half of the damage. In high dimensions a few points become everyone's neighbour. Radovanović and two colleagues measured that in 2010, on a broad evidence base: “In all, we examined 50 real data sets from well known sources, belonging to three categories: UCI multidimensional data, gene expression microarray data, and textual data in the bag-of-words representation”. Across those sets, the Spearman correlation between dimensionality d and the skewness of 10-occurrences is 0.62. As d rises, a shrinking handful of rows captures the 10-nearest-neighbour lists of everything else.

Engineers are still building around the effect. A 2025 AAAI paper turns hub detection into a sampling problem, finding hubs from 10% of the points under dot-product, L1, L2 and dynamic-time-warping distances. Its motive is stated plainly: “The hubs' effects, called the hubness phenomenon, degrade the performance of kNN based models in high dimensions”.

So the layers are: useful signal dimensions, where proximity relates to the target; noisy dimensions that add distance without adding relevance; concentration, where nearest and farthest converge; and unstable neighborhoods, which now has a name and a number rather than a warning. The test is empirical. Measure the gap between nearest and farthest distance on your own queries, and count how often the same rows appear in everyone else's neighbour lists.

Standardization gives features comparable variance rather than comparable meaning. A one-standard-deviation change in blood pressure and a one-standard-deviation change in age become numerically similar even if their domain relevance differs.

Robust scaling, transformations, clipping, and domain weights can help, but each changes the neighborhood definition and must be fit within the training boundary. Note how specific a scaling convention has to be before it is reproducible. R's `daisy` does not say "scaled". It names the operation: each variable is “first standardized by dividing each entry by the range of the corresponding variable, after subtracting the minimum value; consequently the rescaled variable has range [0,1], exactly”. That is the level of detail a scaling decision needs to be written down at.

Numeric, binary, categorical, cyclic, ordinal, and set-valued fields do not share one natural subtraction rule. One-hot encoding plus Euclidean distance is a baseline, not a proof of meaningful similarity.

Sometimes separate candidate filters and within-group distances are clearer than one global metric.

One such designed geometry was written down in Biometrics in 1971, by J. C. Gower. His general coefficient distinguishes “Dichotomous, qualitative, and quantitative variates”, then scores each type by its own rule. “For qualitative characters we set sᵢⱼₖ = 1 if the two individuals i and j agree in the kth character and sᵢⱼₖ = 0 if they differ”. “For quantitative characters … we set sᵢⱼₖ = 1 − |xᵢ − xⱼ|/Rₖ. Here Rₖ is the range of character k and may be the total range in the population or the range in the sample.” A second quantity carries missing data: δᵢⱼₖ, “equal to 1 when character k can be compared for i and j, and 0 otherwise”. The similarity is then “the average score taken over all possible comparisons”. Absence enters the definition, instead of being imputed before it.

The aim was practical, and Gower said so: the coefficient “It is particularly suitable for including in computer programs because it can cope with a variety of different data-types without any reprogramming”. He records that it had been used in computer programs since 1960.

That aim is now checkable in shipping software rather than in a fifty-year-old sentence. R's `cluster` package implements the coefficient as `daisy(metric = "gower")` and reaches for it on its own. Its reference manual states that “The handling of nominal, ordinal, and (a)symmetric binary data is achieved by using the general dissimilarity coefficient of Gower (1971)”. Each variable is “first standardized by dividing each entry by the range of the corresponding variable, after subtracting the minimum value; consequently the rescaled variable has range [0,1], exactly”. And “missing values in a row of x are not included in the dissimilarities involving that row”. One function and one argument buy you per-type scoring, range standardisation, and missing values excluded from the comparisons they would have corrupted. That is a different default from imputing them and then reaching for Euclidean distance.

Aggregate accuracy alone can hide nonsensical neighborhoods. Select anchor cases that are common, rare, boundary, and operationally important. Read the nearest and farthest pairs with a domain expert. Decompose each distance to show which features drove it. Perturb one field and measure how neighbor order moves. Compare metrics, scalings and representations against each other. Then validate downstream, confirming that better semantic neighborhoods improve the actual task. The MNIST column above is what step five looks like when it is done properly: one benchmark, one classifier rule, the distance swapped, and the error rate read off each time.

Supervised metric learning or learned embeddings can pull same-label cases together and push others apart. The resulting geometry inherits label quality, sampling, objective choices, and protected-attribute proxies.

The gain is real and measurable in the model's own units. Weinberger and Saul held the kNN rule fixed and learned a Mahalanobis metric instead, and published the numbers in 2009. On the 20 Newsgroups data set: “The best result for LMMN on this data set improved significantly over kNN classification using Euclidean distances and PCA (with 14.98% versus 48.57% and 18.22% test error rates).” The misspelling “LMMN” is as printed in the paper. On MNIST — 70,000 inputs, 784 features reduced to 164, 60,000 training and 10,000 test examples — the test error moved from 2.12% with Euclidean kNN to 1.72% with LMNN. Hosseini and Hammer report the same benchmark at 164 dimensions in 2018: 97.57 accuracy for kNN, 98.28 for sp-lmnn, 98.31 for mp-lmnn.

What the learned geometry does not fix is who the threshold is fair to. NIST ran its Face Recognition Vendor Test Part 3 in December 2019: 18.27 million images of 8.49 million people, 189 algorithms from 99 developers. Across demographic groups, false-positive rates varied “by factors of 10 to beyond 100 times”. The Executive Summary is specific about the direction: “Using the higher quality Application photos, false positive rates are highest in West and East African and East Asian people, and lowest in Eastern European individuals.” Krishnapriya and four colleagues report the same class of effect on the MORPH data set: “For a fixed decision threshold, the African-American image cohort has a higher false match rate and a lower false non-match rate.” One embedding, one distance, one global cut-off — and an error rate that depends on who is being compared.

Inspect retrieval examples and failure slices even when the representation was learned end to end.