Curse of Dimensionality: Distance Concentration and the Vanishing Inscribed Ball

A ring of posts as tall as the distance from the gold query ball to each random point. Raise the dimension and the posts all level out; the glass disc marks the mean. Drag to orbit.

Switch to 2D
Controls

Presets

Parameters

Quality

Camera

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.

Loading model...
Loading Blender model...
-
-
Made with 🟠 Blender · Three.js