@article {15610,
	title = {Space-time tradeoffs for approximate nearest neighbor searching},
	journal = {Journal of the ACM (JACM)},
	volume = {57},
	year = {2009},
	month = {2009/11//},
	pages = {1:1{\textendash}1:54 - 1:1{\textendash}1:54},
	abstract = {Nearest neighbor searching is the problem of preprocessing a set of n point points in d-dimensional space so that, given any query point q, it is possible to report the closest point to q rapidly. In approximate nearest neighbor searching, a parameter ϵ > 0 is given, and a multiplicative error of (1 + ϵ) is allowed. We assume that the dimension d is a constant and treat n and ϵ as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space O(n) and query time O(log n + 1/ϵd-1) to high-space solutions having space roughly O((n log n)/ϵd) and query time O(log (n/ϵ)). We show that there is a single approach to this fundamental problem, which both improves upon existing results and spans the spectrum of space-time tradeoffs. Given a tradeoff parameter γ, where 2 <= γ <= 1/ϵ, we show that there exists a data structure of space O(nγd-1 log(1/ϵ)) that can answer queries in time O(log(nγ) + 1/(ϵγ)(d-1)/2. When γ = 2, this yields a data structure of space O(n log (1/ϵ)) that can answer queries in time O(log n + 1/ϵ(d-1)/2). When γ = 1/ϵ, it provides a data structure of space O((n/ϵd-1)log(1/ϵ)) that can answer queries in time O(log(n/ϵ)). Our results are based on a data structure called a (t,ϵ)-AVD, which is a hierarchical quadtree-based subdivision of space into cells. Each cell stores up to t representative points of the set, such that for any query point q in the cell at least one of these points is an approximate nearest neighbor of q. We provide new algorithms for constructing AVDs and tools for analyzing their total space requirements. We also establish lower bounds on the space complexity of AVDs, and show that, up to a factor of O(log (1/ϵ)), our space bounds are asymptotically tight in the two extremes, γ = 2 and γ = 1/ϵ.},
	keywords = {nearest neighbor searching, space-time tradeoffs},
	isbn = {0004-5411},
	doi = {10.1145/1613676.1613677},
	url = {http://doi.acm.org/10.1145/1613676.1613677},
	author = {Arya,Sunil and Malamatos,Theocharis and Mount, Dave}
}
@conference {15544,
	title = {Efficient Kriging via Fast Matrix-Vector Products},
	booktitle = {Aerospace Conference, 2008 IEEE},
	year = {2008},
	month = {2008/03//},
	pages = {1 - 7},
	abstract = {Interpolating scattered data points is a problem of wide ranging interest. Ordinary kriging is an optimal scattered data estimator, widely used in geosciences and remote sensing. A generalized version of this technique, called cokriging, can be used for image fusion of remotely sensed data. However, it is computationally very expensive for large data sets. We demonstrate the time efficiency and accuracy of approximating ordinary kriging through the use of fast matrix-vector products combined with iterative methods. We used methods based on the fast Multipole methods and nearest neighbor searching techniques for implementations of the fast matrix-vector products.},
	keywords = {cokriging technique, fast matrix-vector products, fast multipole methods, geophysical techniques, image fusion, Interpolation, iterative methods, nearest neighbor searching, optimal scattered data estimator, Remote sensing, remotely sensed data, scattered data points, sensor fusion, time efficiency},
	doi = {10.1109/AERO.2008.4526433},
	author = {Memarsadeghi,N. and Raykar,V.C. and Duraiswami, Ramani and Mount, Dave}
}
@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.}
}
