Просмотр кода страницы Locality-sensitive hashing

'''Locality-sensitive hashing'''  — [[вероятностный метод]] понижения размерности многомерных данных. Основная идея состоит в таком подборе [[хеш-функция|хеш-функций]] для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину
Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска ''n''-мерных векторов, «похожих» на искомый шаблон.

LSH является одним из наиболее популярных на сегодняшний день приближённых алгоритмов поиска ближайших соседей (Approximate Nearest Neighbor, ANN). LSH в этом подходе отображает множество точек в высокоразмерном пространстве в множество ячеек, т. е. в хеш-таблицу. В отличие от традиционных хешей, LSH обладает свойством чувствительности к местоположению (locality-sensitive hash), благодаря чему способен помещать соседние точки в одну и ту же ячейку.


== Ссылки ==
* [http://infolab.stanford.edu/~ullman/mmds.html#original Mining of Massive Datasets. Anand Rajaraman and Jeff Ullman п.3.4]
* [http://web.mit.edu/andoni/www/LSH/index.html Alex Andoni’s LSH homepage]
* [http://lshkit.sourceforge.net/ LSHKIT: A C++ Locality Sensitive Hashing Library]
* [https://web.archive.org/web/20101203074412/http://www.vision.caltech.edu/malaa/software/research/image-search/ Caltech Large Scale Image Search Toolbox]: a Matlab toolbox implementing several LSH hash functions, in addition to Kd-Trees, Hierarchical K-Means, and Inverted File search algorithms.
* [https://web.archive.org/web/20070322212926/http://infolab.stanford.edu/~manku/papers/07www-duplicates.pdf Simhash at Google]
* [https://github.com/salviati/slash Slash: A C++ LSH library, implementing Spherical LSH by Terasawa, K., Tanaka, Y]
* [https://web.archive.org/web/20170830193509/http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LSHForest.html#sklearn.neighbors.LSHForest LSH Forest: Locality Sensitive Hashing forest implementation - SciKitLearn]
* [http://dataconomy.com/2017/06/locality-sensitive-hashing-pydata/ Deduplicating Massive Datasets With Locality Sensitive Hashing - Dataconomy]


[[Категория:Алгоритмы поиска]]
[[Category:Scripting Tutorials]]