From The Similarity Search Wiki

Open Problems || Links || Researchers || Bibliography

The Similarity Search Wiki

The purpose of this wiki is to collect links, people, ideas, keywords, papers, slides, code and data sets on nearest neighbors in a single place.

## Contents |

To preprocess a database of *N* objects so that given a query object,
one can effectively determine its nearest neighbors in database.

Name of the problem: nearest neighbors, *k* nearest neighbors (*k*NN, *k*-NN), nearset neighbor search, proximity search, similarity search, approximate nearest neighbors (ANN), range queries, maximal intersection queries, post-office problem, partial match, best match file searching, best match retrieval, sequence nearest neighbors (SNN).

locality-sensitive hashing (LSH), low-distortion embeddings, k-d trees, kd-trees, metric trees, M-trees, R*-trees, vp-trees, vantage point trees, vantage point forest, multi-vantage point tree, bisector trees, Orchard's algorithm, random projections, fixed queries tree, Voronoi tree, BBD-tree, min-wise independent permutations, Burkhard-Keller tree, generalized hyperplane tree, geometric near-neighbor access tree (GNAT), approximating eliminating search algorithm (AESA), inverted index, spatial approximation tree (SAT), sketches.

*k*-nearest neighbor classification algorithm, image similarity identification, audio similarity identification, fingerprint search, audio/video compression (MPEG), optical character recognition, coding theory, function approximation, recommendation systems, near-duplicate detection, targeting on-line ads, distributional similarity computation, spelling correction, nearest neighbor interpolation.

Companies that tackle big data problems with similarity exist:

- simMachines offers a high performance similarity search engine for large datasets along with support and consulting services.

All-nearest-neighbors problem, indexing methods, spatial index, Voronoi diagram, spatial access methods (SAM), multidimensional access methods, closest pair, indexing algorithm, intrinsic dimension, Johnson-Lindenstrauss lemma, Johnson-Lindenstrauss transform, large-scale algorithms, scalability, dimensionality reduction, high dimensions, curse of dimensionality, high-dimensional spaces, cell probe model, metric spaces, Euclidean space, brunch-and-bound search, divide and conquer, massive data sets, metric embeddings, cell probe complexity, spatial data structures, Euclidean *k*-median problem, point sampling.

Did you find a mistake or do you have a suggestion/addition? You canedit the wiki by yourself, or you can the webmaster with your suggestions/corrections/additions. The documentation for editing the wiki can be found here.

Thanks for visiting this wiki!