Locality-sensitive hashing: различия между версиями

Материал из Поле цифровой дидактики
(стилевые правки, пунктуация)
 
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Locality-sensitive hashing''' ('''LSH'''<ref>{{статья
'''Locality-sensitive hashing'''  — [[вероятностный метод]] понижения размерности многомерных данных. Основная идея состоит в таком подборе [[хеш-функция|хеш-функций]] для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину
|заглавие=Approximate nearest neighbors: towards removing the curse of dimensionality
Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска ''n''-мерных векторов, «похожих» на искомый шаблон.
|издание=Proc. of 30th STOC'98 Proceedings of the thirtieth annual ACM symposium on Theory of computing
|страницы=604—613
|ссылка=http://dl.acm.org/citation.cfm?id=276876
|isbn=0-89791-962-9
|doi=10.1145/276698.276876
|язык=en
|тип=journal
|автор=Piotr Indyk; Rajeev Motwani
|год=1998}}</ref>) — [[вероятностный метод]] понижения размерности многомерных данных. Основная идея состоит в таком подборе [[хеш-функция|хеш-функций]] для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину<ref>{{cite web|author=A. Rajaraman and J. Ullman|url=http://infolab.stanford.edu/~ullman/mmds.html|title=Mining of Massive Datasets, Ch. 3.4|year=2010|access-date=2013-09-17|archive-date=2013-08-18|archive-url=https://web.archive.org/web/20130818235945/http://infolab.stanford.edu/%7Eullman/mmds.html|deadlink=no}}</ref>. Один из способов борьбы с [[Проклятие размерности|«проклятием размерности»]] при поиске и анализе многомерных данных, которое заключается в том, что при росте размерности исходных данных поиск по индексу ведёт себя хуже, чем последовательный просмотр. Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска ''n''-мерных векторов, «похожих» на искомый шаблон.


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


Преимуществами LSH являются: 1) простота использования; 2) строгая теория, подтверждающая хорошую производительность алгоритма; 3) LSH совместим с любой [[Lp (пространство)|нормой <math>L_p</math>]] при <math>0 < p \leq 2</math>. LSH можно использовать с [[Евклидова метрика|евклидовой метрикой]] и с [[Расстояние городских кварталов|манхэттенским расстоянием]]. Существуют также варианты для [[Расстояние Хэмминга|расстояния Хэмминга]] и [[Коэффициент Отиаи|косинусного коэффициента]]<ref>{{статья
|заглавие=Locality-sensitive hashing for finding nearest neighbors
|ссылка=http://ieeexplore.ieee.org/document/4472264/
|язык=en
|тип=journal
|автор=M. Slaney; M. Casey
|год=2008}}</ref>.
== Примечания ==
{{примечания}}


== Ссылки ==
== Ссылки ==
Строка 35: Строка 16:




{{перевести|en|Locality-sensitive hashing}}
{{math-stub}}
{{DEFAULTSORT:Locality Sensitive Hashing}}
[[Категория:Теория информации]]
[[Категория:Хеширование]]
[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы поиска]]
[[Category:Scripting Tutorials]]

Текущая версия на 19:57, 15 декабря 2022

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

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


Ссылки

Источник — http://digida.mgpu.ru/index.php?title=Locality-sensitive_hashing&oldid=6572