Nearest Neighbor Search

1. Introduction 

 Nearest neighbor search (NNS), also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest (or most similar) points. Closeness (similarity) is typically expressed in terms of a dissimilarity function: the less similar the target, the larger the function values. The nearest-neighbor (NN) search problem is formally defined as follows: given a set S of points in a space M and a query point q∈M, find the closest point in S to q. Most commonly M is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, M is taken to be the d-dimensional vector space where dissimilarity is measured using the Euclidean distance, Manhattan distance or other distance metric. However, the dissimilarity function can be arbitrary. 

2. Methods

  Various solution to the NNS problem have been proposed. The quality and usefulness of the algorithms are determined by the time complexity of queries as well as the space complexity of any search data structures that must be maintained. The informal observation usually referred to as the curse of dimensionality states that there is no general-purpose solution for NNS in high-dimensional Euclidean space using polynomial preprocessing and polylogarithmic search time. 

  1) Linear search

   Computing the distance from the query point to every other point in the database is the simplest solution to the NNS problem. We sometimes call it as the naive approach, has a running time of O(dN) where N is the cardinality of S and d is the dimensionality of M. Since there are no search data structures to maintain, the linear search has no space complexity beyond the storage of the database. 

   2)