Curse of Dimensionality Distance Profile: Sorted Lp Distances and Contrast (2D)

Sorted distances from one query point to n random points in d dimensions, in units of the mean: watch the bars flatten as d grows.

Switch to 3D
Controls

Presets

Parameters

Model checks

The science

Distance concentration. Draw n points uniformly in the unit cube [0,1]d and one query point. For two independent uniform coordinates E|X-Y|p = 2/((p+1)(p+2)) and E|X-Y|2p = 2/((2p+1)(2p+2)), so the sum S = ∑i|xi-yi|p has mean d·m1 and variance d·v1 exactly. The Lp distance is D = S1/p, and by the delta method its coefficient of variation is about sqrt(v1)/(m1 p √d), which falls like 1/√d: in high dimension every point is almost equally far, the relative contrast (Dmax-Dmin)/Dmin collapses and "nearest neighbour" carries little information (Beyer, Goldstein, Ramakrishnan and Shaft, ICDT 1999, "When is nearest neighbor meaningful?").

Volume. The ball of radius 1/2 inscribed in the cube has volume Vd = πd/2/(Γ(d/2+1) 2d); it is 79 % of the cube at d = 2, 1.6 % at d = 8 and about 10-8 at d = 20, so almost all the volume sits in the corners.

Simplifications. Uniform i.i.d. data only; real data lie on low-dimensional manifolds, which is why nearest-neighbour search still works on embeddings with low intrinsic dimension. The delta-method CV is asymptotic (checked to a few percent). Checks: Monte Carlo mean and variance of S against the exact moments (4.5 sigma), recursion versus Gamma-function ball volume, hit fraction of points in the inscribed ball, and the measured CV against the delta-method value.

-
-