The goal of this article is twofold. In the first part, we survey a family of nearest neighbor algorithms that are based on the concept of localitysensitive hashing. Many of these algorithm have already been successfully applied in a variety of practical scenarios. In the second part of this article, we describe a recently discovered hashing-based algorithm, for the case where the objects are points in the d-dimensional Euclidean space. As it turns out, the performance of this algorithm is provably near-optimal in the class of the locality-sensitive hashing algorithms. 1 See section 2.4 for more information about exact algorithms. Abstract I n this article, we give an overview of efficient algorithms for the approximate and exact nearest neighbor problem. The goal is to preprocess a dataset of objects (e.g., images) so that later, given a new query object, one can quickly return the dataset object that is most similar to the query. The problem is of significant interest in a wide variety of areas.
Hash-based techniques use a set of locality-sensitive hashing (LSH) functions REF .
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
CACM
Computer Science