The curse of dimensionality

The curse of dimensionality is a set of counter-intuitive effects as the number of dimensions $d$ grows:

• Data becomes sparse. To cover the unit cube with points spaced 0.1 apart takes $10$ points in 1-D, $100$ in 2-D and $10^{10}$ in 10-D.\n- Distances concentrate. The nearest and farthest neighbours end up at almost the same distance, so 'nearest' carries little information — bad news for k-NN and clustering.\n- Volume moves to the edges. In high dimensions, almost all of a ball's volume lies in a thin shell near its surface.

The required amount of data grows exponentially with $d$ for methods that rely on local neighbourhoods.