Nearest Neighbour Searches and the Curse of Dimensionality
Rosalind B. Marimont, Marvin B. Shapiro · IMA Journal of Applied Mathematics · 1979
It is shown that efficiency of cut-off algorithms for nearest neighbour searches depends on the ratio of variance in a lower bound space B to variance in the original space L. The usual choice of a one dimensional B space fails for a high dimensional L space because this ratio is then low. If the dimensionality of B is about half that of L the equivalent of no more than 75% of the full distance computations need be done, independent of the dimensionality of L space. If the variance in B space can be increased by either sorting or the principal components transformation performance is appreciably better.