Locality-sensitive hashing

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

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

Примечания[править | править исходный текст]

  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).

Ссылки[править | править исходный текст]