Title |
-Nearest Neighbor Search in High Dimensions.
| |

Authors |
Helmut
Alt and
Laura Heinrich-Litan.
| |

Published |
In Proceedings of the 17th ACM Symposium on Computational Geometry, Boston, June 2001.
| |

Abstract |
We present an algorithm for solving the nearest neighbor problem with respect to
-distance.
It requires no preprocessing and storage only for the point set P. Its average runtime assuming that the set P
of n points is drawn randomly from the unit cube $[0,1]^{d}$ under uniform distribution is essentially $\Theta (nd/ln\; n)$
thereby improving the brute-force method by a factor of $\Theta (1/ln\; n)$. Several generalizations
of the method are also presented, in particular to other well-behaved probability distributions
and to the important problem of finding the k nearest neighbors to a query point.
| |

Downloading | [ps] [pdf] |