Locality-sensitive hashing

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Преимуществами LSH являются: 1) простота использования; 2) строгая теория, подтверждающая хорошую производительность алгоритма; 3) LSH совместим с любой нормой при . LSH можно использовать с евклидовой метрикой, с манхэттенским расстоянием. Существуют также варианты для расстояния Хэмминга и косинусного коэффициента[3].

Примечания[править | править вики-текст]

  1. Piotr Indyk; Rajeev Motwani (1998). «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: 604–613. DOI:10.1145/276698.276876.
  2. A. Rajaraman and J. Ullman. Mining of Massive Datasets, Ch. 3.4 (2010).
  3. M. Slaney; M. Casey (2008). «Locality-sensitive hashing for finding nearest neighbors».

Ссылки[править | править вики-текст]