"Approximate Nearest Neighbors"
Speaker:	Guilherme Fonseca
When/where:  	Noon Monday 3/14 in CSIC 2107
Category:	CATS

Approximate Nearest Neighbors

Finding the nearest neighbor (NN) of a query point q, among a set of n
points in d-dimensional Euclidean space, is a fundamental geometric data
structures problem. Unfortunately, efficient solutions are not known for
high dimensions. We consider the problem of approximate nearest neighbor
(ANN), which consists of finding a point p such that dist(p,q) <= (1
+eps)dist(NN(q),q), for 0 < eps < 1/2. We show how to construct a linear
size quad-tree based data structure that answers ANN queries in
logarithmic time. Lastly, we present techniques that lead to improved
performance, especially by reducing the size dependence on 1/eps and d.