Locality-sensitive hashing: различия между версиями
(стилевые правки, пунктуация) |
Patarakin (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Locality-sensitive hashing''' | '''Locality-sensitive hashing''' — [[вероятностный метод]] понижения размерности многомерных данных. Основная идея состоит в таком подборе [[хеш-функция|хеш-функций]] для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину | ||
Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска ''n''-мерных векторов, «похожих» на искомый шаблон. | |||
LSH является одним из наиболее популярных на сегодняшний день приближённых алгоритмов поиска ближайших соседей (Approximate Nearest Neighbor, ANN). LSH в этом подходе отображает множество точек в высокоразмерном пространстве в множество ячеек, т. е. в хеш-таблицу. В отличие от традиционных хешей, LSH обладает свойством чувствительности к местоположению (locality-sensitive hash), благодаря чему способен помещать соседние точки в одну и ту же ячейку. | LSH является одним из наиболее популярных на сегодняшний день приближённых алгоритмов поиска ближайших соседей (Approximate Nearest Neighbor, ANN). LSH в этом подходе отображает множество точек в высокоразмерном пространстве в множество ячеек, т. е. в хеш-таблицу. В отличие от традиционных хешей, LSH обладает свойством чувствительности к местоположению (locality-sensitive hash), благодаря чему способен помещать соседние точки в одну и ту же ячейку. | ||
== Ссылки == | == Ссылки == | ||
Строка 35: | Строка 16: | ||
[[Категория:Алгоритмы поиска]] | [[Категория:Алгоритмы поиска]] | ||
[[Category:Scripting Tutorials]] |
Текущая версия на 19:57, 15 декабря 2022
Locality-sensitive hashing — вероятностный метод понижения размерности многомерных данных. Основная идея состоит в таком подборе хеш-функций для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска n-мерных векторов, «похожих» на искомый шаблон.
LSH является одним из наиболее популярных на сегодняшний день приближённых алгоритмов поиска ближайших соседей (Approximate Nearest Neighbor, ANN). LSH в этом подходе отображает множество точек в высокоразмерном пространстве в множество ячеек, т. е. в хеш-таблицу. В отличие от традиционных хешей, LSH обладает свойством чувствительности к местоположению (locality-sensitive hash), благодаря чему способен помещать соседние точки в одну и ту же ячейку.
Ссылки
- Mining of Massive Datasets. Anand Rajaraman and Jeff Ullman п.3.4
- Alex Andoni’s LSH homepage
- LSHKIT: A C++ Locality Sensitive Hashing Library
- 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.
- Simhash at Google
- Slash: A C++ LSH library, implementing Spherical LSH by Terasawa, K., Tanaka, Y
- LSH Forest: Locality Sensitive Hashing forest implementation - SciKitLearn
- Deduplicating Massive Datasets With Locality Sensitive Hashing - Dataconomy