Locality-sensitive hashing

Locality-sensitive hashing (LSH) — вероятностный метод понижения размерности многомерных данных. Основная идея состоит в таком подборе хеш-функций для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину. Один из способов борьбы с «проклятием размерности» при поиске и анализе многомерных данных, которое заключается в том, что при росте размерности исходных данных поиск по индексу ведёт себя хуже, чем последовательный просмотр. Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска n-мерных векторов, «похожих» на искомый шаблон. LSH является одним из наиболее популярных на сегодняшний день приближённых алгоритмов поиска ближайших соседей (Approximate Nearest Neighbor, ANN). LSH в этом подходе отображает множество точек в высокоразмерном пространстве в множество ячеек, т. е. в хеш-таблицу. В отличие от традиционных хешей, LSH обладает свойством чувствительности к местоположению (locality-sensitive hash), благодаря чему способен помещать соседние точки в одну и ту же ячейку. Преимуществами LSH являются: 1) простота использования; 2) строгая теория, подтверждающая хорошую производительность алгоритма; 3) LSH совместим с любой нормой L p {\displaystyle L_{p}} при 0 < p ≤ 2 {\displaystyle 0<p\leq 2} . LSH можно использовать с евклидовой метрикой и с манхэттенским расстоянием. Существуют также варианты для расстояния Хэмминга и косинусного коэффициента.

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

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

Преимуществами LSH являются: 1) простота использования; 2) строгая теория, подтверждающая хорошую производительность алгоритма; 3) LSH совместим с любой нормой L p {\displaystyle L_{p}} при 0 < p ≤ 2 {\displaystyle 0<p\leq 2} . LSH можно использовать с евклидовой метрикой и с манхэттенским расстоянием. Существуют также варианты для расстояния Хэмминга и косинусного коэффициента^[3].

Примечания

[править | править код]

1. ↑ Piotr Indyk; Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality (англ.) // Proc. of 30th STOC'98 Proceedings of the thirtieth annual ACM symposium on Theory of computing : journal. — 1998. — P. 604—613. — ISBN 0-89791-962-9. — doi:10.1145/276698.276876. Архивировано 19 февраля 2015 года.
2. ↑ A. Rajaraman and J. Ullman. Mining of Massive Datasets, Ch. 3.4  (2010). Дата обращения: 17 сентября 2013. Архивировано 18 августа 2013 года.
3. ↑ M. Slaney; M. Casey. Locality-sensitive hashing for finding nearest neighbors (англ.) : journal. — 2008. Архивировано 30 августа 2017 года.

Ссылки

[править | править код]

• 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

В другом языковом разделе есть более полная статья Locality-sensitive hashing (англ.).

Вы можете помочь проекту, расширив текущую статью с помощью перевода

Это заготовка статьи по математике. Помогите Википедии, дополнив её.