Thu Jun 6 14:46:17 EDT 2013

Distance in high-dimensional vector spaces

From [2]:

    ... 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.

Is this related to the idea that the volume of a high dimensional
sphere[3] is small compared to its bounding cube?  I don't see the

The basic problem seems to be that high-dimensional
discrete-dimensional spaces are "very connected" in a way that is not
immediately clear on an intuitive sense.  Our usual 1,2,3-dimensional
view is very particular, and doesn't generalize to larger numbers.

[1] http://spin.atomicobject.com/2013/05/06/k-nearest-neighbor-racket/
[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
[3] http://en.wikipedia.org/wiki/N-sphere#n-ball