Locality-sensitive hashing - История изменений

Patarakin в 16:57, 15 декабря 2022

2022-12-15T16:57:13Z

@@ Строка 1: / Строка 1: @@
-'''Locality-sensitive hashing''' ('''LSH'''<ref>{{статья
+'''Locality-sensitive hashing'''  — [[вероятностный метод]] понижения размерности многомерных данных. Основная идея состоит в таком подборе [[хеш-функция|хеш-функций]] для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину
-|заглавие=Approximate nearest neighbors: towards removing the curse of dimensionality
+Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска ''n''-мерных векторов, «похожих» на искомый шаблон.
 LSH является одним из наиболее популярных на сегодняшний день приближённых алгоритмов поиска ближайших соседей (Approximate Nearest Neighbor, ANN). LSH в этом подходе отображает множество точек в высокоразмерном пространстве в множество ячеек, т. е. в хеш-таблицу. В отличие от традиционных хешей, LSH обладает свойством чувствительности к местоположению (locality-sensitive hash), благодаря чему способен помещать соседние точки в одну и ту же ячейку.
 == Ссылки ==
@@ Строка 35: / Строка 16: @@
 [[Категория:Алгоритмы поиска]]

Patarakin: 1 версия импортирована

2022-10-19T17:55:03Z

1 версия импортирована

← Предыдущая версия		Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>Fifis: стилевые правки, пунктуация

2022-09-11T09:32:14Z

стилевые правки, пунктуация

Новая страница

'''Locality-sensitive hashing''' ('''LSH'''<ref>{{статья
|заглавие=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
|ссылка=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 являются: 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>.

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://infolab.stanford.edu/~ullman/mmds.html#original Mining of Massive Datasets. Anand Rajaraman and Jeff Ullman п.3.4]
* [http://web.mit.edu/andoni/www/LSH/index.html Alex Andoni’s LSH homepage]
* [http://lshkit.sourceforge.net/ LSHKIT: A C++ Locality Sensitive Hashing Library]
* [https://web.archive.org/web/20101203074412/http://www.vision.caltech.edu/malaa/software/research/image-search/ 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.
* [https://web.archive.org/web/20070322212926/http://infolab.stanford.edu/~manku/papers/07www-duplicates.pdf Simhash at Google]
* [https://github.com/salviati/slash Slash: A C++ LSH library, implementing Spherical LSH by Terasawa, K., Tanaka, Y]
* [https://web.archive.org/web/20170830193509/http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.LSHForest.html#sklearn.neighbors.LSHForest LSH Forest: Locality Sensitive Hashing forest implementation - SciKitLearn]
* [http://dataconomy.com/2017/06/locality-sensitive-hashing-pydata/ Deduplicating Massive Datasets With Locality Sensitive Hashing - Dataconomy]

{{перевести|en|Locality-sensitive hashing}}
{{math-stub}}

{{DEFAULTSORT:Locality Sensitive Hashing}}

[[Категория:Теория информации]]
[[Категория:Хеширование]]
[[Категория:Алгоритмы поиска]]