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