@article {15611,
	title = {An optimal algorithm for approximate nearest neighbor searching fixed dimensions},
	journal = {Journal of the ACM (JACM)},
	volume = {45},
	year = {1998},
	month = {1998/11//},
	pages = {891 - 923},
	abstract = {Consider a set of S of n data points  in real d-dimensional space, Rd, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ Rd, is the closest point of S to q can be reported quickly. Given any positive real \&egr;, data point p is a (1 +\&egr;)-approximate nearest neighbor of q if its distance from q is within a factor of (1 + \&egr;) of the distance to the true nearest neighbor. We show that it is possible to preprocess a    set of n points in     Rd in O(dn log n) time and O(dn) space, so that given a query point  q  ∈ Rd, and \&egr; > 0, a (1 + \&egr;)-approximate nearest neighbor of q can be computed in O(cd, \&egr; log n) time, where cd,\&egr;<=d  1 + 6d/e;d is a factor depending only on dimension and \&egr;. In general, we show that given an integer k >= 1, (1 + \&egr;)-approximations  to the  k nearest neighbors of q can  be computed in additional O(kd log n) time.},
	keywords = {Approximation algorithms, Box-decomposition trees, closet-point queries, nearest neighbor searching, post-office problem, priority search},
	isbn = {0004-5411},
	doi = {10.1145/293347.293348},
	url = {http://doi.acm.org/10.1145/293347.293348},
	author = {Arya,Sunil and Mount, Dave and Netanyahu,Nathan S. and Silverman,Ruth and Wu,Angela Y.}
}
