Abstract

The nearest neighbor problem is defined as follows: given a set of n points in a d-dimensional space, build a data structure which, given any query point q, finds a data point closest to q. The problem has numerous applications, especially for large values of d.

In this talk I will present an overview of old and new algorithms for solving this problem, as well as its variants.