On the efficiency of nearest neighbor searching with data clustered in lower dimensions

Nearest neighbor searching is an important and fundamental problem in the field of geometric data structures. Given a set S of n data points in real d-dimensional space, R d, we wish to preprocess these points so that, given any query point q ∈ R d, the data point nearest to q can be reported quickly. We assume that distances are measured using any Minkowski distance metric, including the Euclidean, Manhattan, and max metrics. Nearest neighbor searching has numerous applications in diverse areas of science.