Everything Is The Same Distance

Simulating what Beyer et al. proved: draw 1,000 points uniformly in $[0,1]^d$ , pick a query point the same way, and record the distance to the nearest and the farthest of the 1,000 (median over repeated trials).

$d$	nearest	farthest	farthest / nearest
2	0.016	1.06	66
10	0.50	1.91	3.8
100	3.33	4.78	1.44
1000	12.16	13.62	1.12

What does the last row mean for a k-NN classifier on 1,000 raw features?

Euclidean distance is the problem specifically; switching to Manhattan distance removes the effect, since it does not square the coordinate gaps.

The farthest of the 1,000 points is only 12% further away than the nearest one, so 'nearest' stops carrying information and the vote is close to a vote among arbitrary training rows.

Nothing about the labels: the ratio only says that brute-force search gets slower with $d$ , which is why k-d trees are used instead.

The neighbors are too few for the dimension, so raising $k$ toward 1,000 restores a meaningful vote.