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

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

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

Примечания

Ссылки

• : a Matlab toolbox implementing several LSH hash functions, in addition to Kd-Trees, Hierarchical K-Means, and Inverted File search algorithms.

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