Nearest neighbor searching and applications
Sunil Arya · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1996
Finding nearest neighbors is among the most fundamental problems in computational geometry with applications to many areas such as pattern recognition, data compression and statistics. The nearest neighbor problem is: given a set of n points in d-dimensional space, $S\subset E\sp{d}$, and given a query point $q\in E\sp{d}$, find the point of S that minimizes the Euclidean distance to q. We assume that the d is a constant, independent of n. Efficient algorithms are known for computing nearest neighbors in low dimensional spaces. But, as dimension increases, the difficulty of solving the nearest neighbor problem, either in time or space, seems to grow extremely rapidly. We show, however, that if one is willing to consider approximate nearest neighbors rather than exact nearest neighbors, it is possible to achieve efficient asymptotic performance for both space and query time, irrespective of input distribution. We also present several practical algorithms for performing nearest neighbor searching in high dimensions. These algorithms draw on data structures such as the k-d tree and the neighborhood graph. We give an empirical analysis of these algorithms in the context of vector quantization, which is a technique used in the compression of speech and images. Our results show that these algorithms attain massive reductions in the running time while suffering little loss in performance. Finally, we analyze the complexity of the k-d tree algorithm for the uniform distribution, taking into account the effect of the boundary. We thus provide a more accurate analysis for realistic instances in high dimensions, where boundary effects are significant.