Locality-sensitive hashing

Материал из Поле цифровой дидактики
Версия от 20:55, 19 октября 2022; Patarakin (обсуждение | вклад) (1 версия импортирована)

Locality-sensitive hashing (LSH<ref>{{#if:Piotr Indyk; Rajeev Motwani|Piotr Indyk; Rajeev Motwani  }}{{#if:http://dl.acm.org/citation.cfm?id=276876 

 | Approximate nearest neighbors: towards removing the curse of dimensionality
 | Approximate nearest neighbors: towards removing the curse of dimensionality

}}{{#if:en 

 | {{#ifexist: Шаблон:ref-en
     | Шаблон:Ref-en
     |  (en)
   }}

}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:Proc. of 30th STOC'98 Proceedings of the thirtieth annual ACM symposium on Theory of computing|и}} 

 |аи= // {{{автор издания}}} Proc. of 30th STOC'98 Proceedings of the thirtieth annual ACM symposium on Theory of computing
 |а= // {{{автор издания}}}
 |и= // Proc. of 30th STOC'98 Proceedings of the thirtieth annual ACM symposium on Theory of computing

}}{{#if:journal| : journal }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:1998|г}} 

 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 1998.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 1998.
 |иг= — {{{издательство}}}, 1998.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — {{{издательство}}}.
 |г= — 1998.

}}{{#if:| — В. {{{выпуск}}}.

}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:| — Т. {{{том}}}.

}}{{#if:| — № {{{номер}}}.

}}{{#if:604—613| — С. 604—613. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.

}}{{#if:0-89791-962-9| — ISBN 0-89791-962-9. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:10.1145/276698.276876| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if: 

 |  [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.

}}{{#if:

|

Этот шаблон использует устаревший параметр «название». Пожалуйста, отредактируйте эту статью, заменив «название» на «заглавие».

}}{{#if:

|

Этот шаблон использует устаревший параметр «город». Пожалуйста, отредактируйте эту статью, заменив «город» на «место».

}}</ref>) — вероятностный метод понижения размерности многомерных данных. Основная идея состоит в таком подборе хеш-функций для некоторых измерений, чтобы похожие объекты с высокой степенью вероятности попадали в одну корзину<ref>Шаблон:Cite web</ref>. Один из способов борьбы с «проклятием размерности» при поиске и анализе многомерных данных, которое заключается в том, что при росте размерности исходных данных поиск по индексу ведёт себя хуже, чем последовательный просмотр. Метод позволяет строить структуру для быстрого приближённого (вероятностного) поиска n-мерных векторов, «похожих» на искомый шаблон.

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

Преимуществами LSH являются: 1) простота использования; 2) строгая теория, подтверждающая хорошую производительность алгоритма; 3) LSH совместим с любой нормой [math]\displaystyle{ L_p }[/math] при [math]\displaystyle{ 0 \lt p \leq 2 }[/math]. LSH можно использовать с евклидовой метрикой и с манхэттенским расстоянием. Существуют также варианты для расстояния Хэмминга и косинусного коэффициента<ref>{{#if:M. Slaney; M. Casey|M. Slaney; M. Casey  }}{{#if:http://ieeexplore.ieee.org/document/4472264/ 

 | Locality-sensitive hashing for finding nearest neighbors
 | Locality-sensitive hashing for finding nearest neighbors

}}{{#if:en 

 | {{#ifexist: Шаблон:ref-en
     | Шаблон:Ref-en
     |  (en)
   }}

}}{{#if:| = {{{оригинал}}} }}{{#switch:{{#if:|а}}{{#if:|и}} 

 |аи= // {{{автор издания}}} {{{издание}}}
 |а= // {{{автор издания}}}
 |и= // {{{издание}}}

}}{{#if:journal| : journal }}{{#if:| / {{{ответственный}}} }}.{{#switch:{{#if:|м}}{{#if:|и}}{{#if:2008|г}} 

 |миг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}, 2008.
 |ми= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}: {{{издательство}}}.
 |мг= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}}} }}, 2008.
 |иг= — {{{издательство}}}, 2008.
 |м= — {{#if:{{{место}}}|{{#switch:{{{место}}}|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.={{ {{{место}}} }}|{{{место}}}.}} }}
 |и= — {{{издательство}}}.
 |г= — 2008.

}}{{#if:| — В. {{{выпуск}}}.

}}{{#if:| — Vol. {{{volume}}}. }}{{#if:| — Band {{{band}}}. }}{{#if:| — Т. {{{том}}}.

}}{{#if:| — № {{{номер}}}.

}}{{#if:| — С. {{{страницы}}}. }}{{#if:| — P. {{{pages}}}. }}{{#if: | — S.</nowiki> {{{seite}}}.

}}{{#if:| — ISBN {{{isbn}}}. }}{{#if:| — ISSN Шаблон:ISSN search link. }}{{#if:| — Шаблон:DOI }}{{#if:| — Шаблон:Bibcode }}{{#if:| — Шаблон:Arxiv }}{{#if: | — PMID {{{pmid}}}. }}{{#if: 

 |  [{{{archiveurl}}} Архивировано] из первоисточника {{#iferror: {{#time: j xg Y | {{{archivedate}}}}} | {{{archivedate}}}}}.

}}{{#if:

|

Этот шаблон использует устаревший параметр «название». Пожалуйста, отредактируйте эту статью, заменив «название» на «заглавие».

}}{{#if:

|

Этот шаблон использует устаревший параметр «город». Пожалуйста, отредактируйте эту статью, заменив «город» на «место».

}}</ref>.

Примечания

1 }} 
       | {{#switch: {{{1}}}
         | узкие = columns reflist-narrow
         | широкие = columns reflist-wide
         | #default = columns
         }}
       | {{#switch: {{{1}}}
         | 1 = 
         | 2 | 3 = columns
         | #default = columns reflist-narrow
         }}
       }}
     | columns
     }}
   }}" style="{{#if: 
   | column-width:{{{colwidth}}};
   | {{#if: 
     | {{#iferror: {{#ifexpr: {{{1}}} > 1 }}
       | {{#switch: {{{1}}}
         | узкие | широкие = 
         | #default = column-width:{{{1}}};
         }}
       }}
     }}
   }} list-style-type: {{#switch: 
   | upper-alpha
   | upper-roman
   | lower-alpha
   | lower-greek
   | lower-roman = {{{group}}}
   | #default = decimal
   }};">

<references group="" responsive="{{#if: 

 | 0
 | {{#if: 
   | {{#iferror: {{#expr: {{{1}}} > 1 }}
     | {{#switch: {{{1}}}
       | узкие | широкие = 1
       | #default = 0
       }}
     | {{#switch: {{{1}}}
       | 1 = 0
       | #default = 1
       }}
     }}
   | 1
   }}
}}"></references>

Ошибка скрипта: Модуля «Check for unknown parameters» не существует.

Ссылки


Шаблон:Перевести Шаблон:Math-stub

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