Nearest-Neighbor Searching and Metric Space Dimensions

Given a set S of points in a metric space with distance function D, the nearest-neighbor searching problem is to build a data structure for S so that for an input query point q, the point s in S that minimizes D(s,q) can be found quickly. We survey approaches to this problem, and its relation to concepts of metric space dimension. Several measures of dimension can be estimated using nearest-neighbor searching, while others can be used to estimate the cost of that searching. In recent years, several data structures have been proposed that are provably good for low dimensional spaces, for some particular measures of dimension. These and other data structures for nearest neighbor searching are surveyed.