Индексные структуры для быстрого поиска по сходству вещественных векторов. I
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144842 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Индексные структуры для быстрого поиска по сходству вещественных векторов. I / Д.А. Рачковский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 168–183. — Бібліогр.: 87 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144842 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1448422025-02-23T18:30:36Z Индексные структуры для быстрого поиска по сходству вещественных векторов. I Індексні структури для швидкого пошуку за схожістю дійсних векторів. I Index structures for fast similarity search of real-valued vectors. I Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь и некоторые теоретические аспекты. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені дійсними векторами. Розглянуто індексні структури на основі локально-чутливого хешування та їхні модифікації. Викладено ідеї конкретних алгоритмів (відомих та нещодавно запропонованих). Обговорено їхній взаємозв’язок і деякі теоретичні аспекти. In this survey paper, we consider index structures for fast similarity search of objects represented by real-valued vectors. Index structures based on locality-sensitive hashing and their modifications are considered. The ideas of specific algorithms, including the recently proposed ones, are outlined. Their interrelations and some theoretical aspects are discussed. Автор благодарен Alex Andoni за разъяснения некоторых аспектов его исследований. 2018 Article Индексные структуры для быстрого поиска по сходству вещественных векторов. I / Д.А. Рачковский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 168–183. — Бібліогр.: 87 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/144842 004.22 + 004.93'11 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| spellingShingle |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рачковский, Д.А. Индексные структуры для быстрого поиска по сходству вещественных векторов. I Кибернетика и системный анализ |
| description |
Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь и некоторые теоретические аспекты. |
| format |
Article |
| author |
Рачковский, Д.А. |
| author_facet |
Рачковский, Д.А. |
| author_sort |
Рачковский, Д.А. |
| title |
Индексные структуры для быстрого поиска по сходству вещественных векторов. I |
| title_short |
Индексные структуры для быстрого поиска по сходству вещественных векторов. I |
| title_full |
Индексные структуры для быстрого поиска по сходству вещественных векторов. I |
| title_fullStr |
Индексные структуры для быстрого поиска по сходству вещественных векторов. I |
| title_full_unstemmed |
Индексные структуры для быстрого поиска по сходству вещественных векторов. I |
| title_sort |
индексные структуры для быстрого поиска по сходству вещественных векторов. i |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2018 |
| topic_facet |
Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144842 |
| citation_txt |
Индексные структуры для быстрого поиска по сходству вещественных векторов. I / Д.А. Рачковский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 168–183. — Бібліогр.: 87 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT račkovskijda indeksnyestrukturydlâbystrogopoiskaposhodstvuveŝestvennyhvektorovi AT račkovskijda índeksnístrukturidlâšvidkogopošukuzashožístûdíjsnihvektorívi AT račkovskijda indexstructuresforfastsimilaritysearchofrealvaluedvectorsi |
| first_indexed |
2025-11-24T10:24:14Z |
| last_indexed |
2025-11-24T10:24:14Z |
| _version_ |
1849666939765391360 |
| fulltext |
Ä.À. ÐÀ×ÊÎÂÑÊÈÉ
ÓÄÊ 004.22 + 004.93�11 ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÁÛÑÒÐÎÃÎ
ÏÎÈÑÊÀ ÏÎ ÑÕÎÄÑÒÂÓ ÂÅÙÅÑÒÂÅÍÍÛÕ
ÂÅÊÒÎÐÎÂ. I
Àííîòàöèÿ. Äàí îáçîð èíäåêñíûõ ñòðóêòóð äëÿ áûñòðîãî ïîèñêà ïî ñõîäñòâó
îáúåêòîâ, ïðåäñòàâëåííûõ âåùåñòâåííûìè âåêòîðàìè. Ðàññìîòðåíû èíäåê-
ñíûå ñòðóêòóðû íà îñíîâå ëîêàëüíî-÷óâñòâèòåëüíîãî õýøèðîâàíèÿ è èõ ìî-
äèôèêàöèè. Èçëîæåíû èäåè êîíêðåòíûõ àëãîðèòìîâ, âêëþ÷àÿ íåäàâíî ïðåä-
ëîæåííûå. Îáñóæäåíà èõ âçàèìîñâÿçü è íåêîòîðûå òåîðåòè÷åñêèå àñïåêòû.
Êëþ÷åâûå ñëîâà: ïîèñê ïî ñõîäñòâó, áëèæàéøèé ñîñåä, áëèæíèé ñîñåä,
èíäåêñíûå ñòðóêòóðû, ëîêàëüíî-÷óâñòâèòåëüíîå õýøèðîâàíèå, ëîêàëüíî-÷óâ-
ñòâèòåëüíàÿ ôèëüòðàöèÿ.
ÂÂÅÄÅÍÈÅ
Ïîèñê ïî ñõîäñòâó — ýòî âàðèàíò èíôîðìàöèîííîãî ïîèñêà, ïðè êîòîðîì îáú-
åêòû èç íåêîòîðîé áàçû (ìíîæåñòâà) îáúåêòîâ, ðåëåâàíòíûå îáúåêòó-çàïðîñó,
îïðåäåëÿþòñÿ ïî çíà÷åíèÿì íåêîòîðûõ ìåð (ôóíêöèé) ñõîäñòâà èëè íåñõîä-
ñòâà (ðàññòîÿíèÿ) ìåæäó ïðåäñòàâëåíèÿìè îáúåêòîâ.
Áóäåì ñ÷èòàòü ïðåäñòàâëåíèÿ îáúåêòîâ è ìåðó ðàññòîÿíèÿ/ñõîäñòâà, ïî êîòî-
ðîé âûïîëíÿåòñÿ ïîèñê, çàäàííûìè. Ïðîùå âñåãî âûïîëíèòü ïîèñê ïî ñõîäñòâó
âû÷èñëåíèåì âåëè÷èí ñõîäñòâ îáúåêòà-çàïðîñà è âñåõ N îáúåêòîâ áàçû è âîçâðà-
ùåíèåì îáúåêòîâ, óäîâëåòâîðÿþùèõ óñëîâèÿì çàïðîñà. Òàêîé «ëèíåéíûé» (èëè
«ïîñëåäîâàòåëüíûé») ïîèñê ÷àñòî îêàçûâàåòñÿ íåäîïóñòèìî ìåäëåííûì, îñîáåí-
íî äëÿ áîëüøèõ áàç, ñëîæíûõ ìíîãîêîìïîíåíòíûõ ïðåäñòàâëåíèé îáúåêòîâ è
âû÷èñëèòåëüíî ñëîæíûõ ìåð ñõîäñòâà.
Îäèí ïîäõîä ê óñêîðåíèþ ëèíåéíîãî ïîèñêà ïî ñõîäñòâó — áûñòðî (õîòÿ
è ïðèáëèæåííî) îöåíèòü âåëè÷èíû âñåõ ðàññòîÿíèé/ñõîäñòâ (ñì. îáçîðû [1, 2]). Äðó-
ãîé ïîäõîä çàêëþ÷àåòñÿ â ïîñòðîåíèè ïî áàçå òàêîé ñòðóêòóðû äàííûõ (èíäåêñíîé
ñòðóêòóðû, ÈÑ), èñïîëüçîâàíèå êîòîðîé ïðè âûïîëíåíèè çàïðîñà ïîèñêà ïî ñõîä-
ñòâó ïîçâîëèëî áû ñîêðàòèòü êîëè÷åñòâî âû÷èñëåíèé ñõîäñòâà îáúåêòà-çàïðîñà
ñ äðóãèìè îáúåêòàìè ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì (ñóáëèíåéíûé ïîèñê îòíî-
ñèòåëüíî N ). Îòìåòèì, ÷òî àëãîðèòìû îáîèõ ïîäõîäîâ çà÷àñòóþ óñêîðÿþò ïîèñê
öåíîé ïîëó÷åíèÿ ðåçóëüòàòîâ, íå ïîëíîñòüþ ñîâïàäàþùèõ ñ ðåçóëüòàòàìè (òî÷íîãî)
ëèíåéíîãî ïîèñêà ïî ñõîäñòâó, ò.å. îáåñïå÷èâàþò ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó.
Îáçîð ÈÑ, ðàçðàáàòûâàåìûõ â ðàìêàõ âòîðîãî ïîäõîäà è íå òðåáóþùèõ ÿâíîãî
äîñòóïà ê ïðåäñòàâëåíèÿì îáúåêòîâ, êðîìå êàê äëÿ âû÷èñëåíèÿ ðàññòîÿíèé/ñõîäñòâ,
ïðåäñòàâëåí â [3]. Â îáçîðå [4] ðàññìîòðåíû ÈÑ ïîèñêà ïî ñõîäñòâó äëÿ îáúåêòîâ —
áèíàðíûõ âåêòîðîâ. Â íàñòîÿùåé ñòàòüå äàí îáçîð îñíîâíûõ òèïîâ ÈÑ äëÿ áûñòðîãî
ïîèñêà ïî ñõîäñòâó îáúåêòîâ, ïðåäñòàâëåííûõ âåùåñòâåííûìè âåêòîðàìè (êîìïî-
íåíòû êîòîðûõ — âåùåñòâåííûå ÷èñëà). Òàêèå âåêòîðû øèðîêî ïðèìåíÿþòñÿ, íà-
ïðèìåð, äëÿ ïðåäñòàâëåíèÿ òåêñòîâ, èçîáðàæåíèé, è äð. [5–9]. Õîòÿ äëÿ âåêòîðîâ
ìîæíî èñïîëüçîâàòü ÈÑ èç [3], âåêòîðû ïðåäîñòàâëÿþò áîëüøå ñðåäñòâ äëÿ èíäåê-
ñèðîâàíèÿ çà ñ÷åò âîçìîæíîñòåé äîñòóïà ê ñâîèì êîìïîíåíòàì è èõ ïîäìíîæåñ-
òâàì, ÿâíîãî çàäàíèÿ ãðàíèö îáëàñòåé âåêòîðíîãî ïðîñòðàíñòâà, ïðèìåíåíèÿ ñïåöèà-
ëèçèðîâàííûõ îïåðàöèé è àëãîðèòìîâ (óñðåäíåíèå, êëàñòåðèçàöèÿ) è äð.
168 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
© Ä.À. Ðà÷êîâñêèé, 2018
Îáçîð ñîñòîèò èç äâóõ ÷àñòåé, íàñòîÿùàÿ ñòàòüÿ ÿâëÿåòñÿ åãî ïåðâîé ÷àñòüþ.
Ðàññìîòðåíû, ãëàâíûì îáðàçîì, ïðàêòè÷åñêè ðåàëèçîâàííûå èëè èìåþùèå ïåð-
ñïåêòèâó òàêîé ðåàëèçàöèè ÈÑ, êîíñòðóèðóåìûå áåç èíôîðìàöèè îò ó÷èòåëÿ.
 äàííîé ÷àñòè îáçîðà îáñóæäàþòñÿ ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó
íà îñíîâå ñîõðàíÿþùåãî ñõîäñòâà õýøèðîâàíèÿ (ðàçä. 2). Ââåäåíèå â ïðîáëåìà-
òèêó ïîèñêà ïî ñõîäñòâó ïðåäñòàâëåíî â ðàçä. 1.
1. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß
Ðàññìîòðèì îïðåäåëåíèÿ èñïîëüçóåìûõ â ÈÑ ðàññòîÿíèé è ñõîäñòâ, òèïû çà-
ïðîñîâ ïîèñêà ïî ñõîäñòâó, ïðîáëåìû òî÷íîãî ïîèñêà è íåîáõîäèìîñòü ïåðå-
õîäà ê ïðèáëèæåííîìó ïîèñêó äëÿ áûñòðîãî âûïîëíåíèÿ çàïðîñîâ, à òàêæå
ïðèíöèïû ïîñòðîåíèÿ è ïðèìåíåíèÿ ÈÑ.
1.1. Ðàññòîÿíèÿ è ñõîäñòâà. Äëÿ îöåíêè ñõîäñòâà ìåæäó îáúåêòàìè èñïîëü-
çóþò ðàññòîÿíèå, ò.å. «íåñõîäñòâî». Áîëüøèì çíà÷åíèÿì ñõîäñòâà ñîîòâåòñòâóþò
ìàëûå çíà÷åíèÿ ðàññòîÿíèÿ. Ìíîãèå ðàññòîÿíèÿ ÿâëÿþòñÿ ìåòðèêàìè, ò.å. ïîä÷è-
íÿþòñÿ ìåòðè÷åñêèì àêñèîìàì, òàêèì êàê íåðàâåíñòâî òðåóãîëüíèêà è äð. Äëÿ
âåùåñòâåííûõ âåêòîðîâ a b, ðàçìåðíîñòè D øèðîêî ïðèìåíÿþòñÿ ðàññòîÿíèÿ
Ìèíêîâñêîãî Ls ðàçëè÷íîãî ïîðÿäêà s: | | | | | |
/
a b� � ��
�
� �
��s i
D
i i
s
s
a b
1
1
. Íàèáîëåå
ðàñïðîñòðàíåíû ìåòðè÷åñêèå ðàññòîÿíèÿ L2 (åâêëèäîâî | | | |a b� 2), L1 (ìàíõýòòå-
íîâî | | | |a b� 1), L� (ðàññòîÿíèå ×åáûøåâà | | | |a b� � ). Ïðè 0 1
s ïîëó÷àåì
äðîáíûå ðàññòîÿíèÿ, êîòîðûå íå ÿâëÿþòñÿ ìåòðèêàìè.
Äëÿ ñõîäñòâ áîëüøèå çíà÷åíèÿ ñîîòâåòñòâóþò áîëåå ñõîäíûì îáúåêòàì. Îäíà èç
ìåð ñõîäñòâà âåêòîðîâ — ñêàëÿðíîå ïðîèçâåäåíèå: sim dot ( , ) ,a b a b� � � � ��i
D
i ia b
1
.
Îòìåòèì, ÷òî | | | | | | | | | | | | ,a b a b a b� � � � � �
2
2
2
2
2
2 2 , à òàêæå òî, ÷òî âåëè÷èíà sim dot ( , )a a
íå ÿâëÿåòñÿ ìàêñèìàëüíî âîçìîæíîé. Êîñèíóñ óãëà ìåæäó âåêòîðàìè îïðåäåëÿ-
åòñÿ êàê cos ( , ) , / (| | | | | | | | )a b a b a b� � � �
2 2 sim cos. Óãîë ìåæäó a, b îïðåäåëÿåò
ðàññòîÿíèå dist arccosang � ( , )a b . Âåêòîðû åäèíè÷íîé åâêëèäîâîé íîðìû
(| | | |a 2 1� ) åùå íàçûâàþò âåêòîðàìè (åâêëèäîâîé) åäèíè÷íîé ñôåðû, êîòîðóþ îáî-
çíà÷àþò S D�1. Óïîðÿäî÷åíèå òàêèõ âåêòîðîâ ïî âîçðàñòàíèþ åâêëèäîâà ðàññòîÿíèÿ
(èëè óãëà) ýêâèâàëåíòíî óïîðÿäî÷åíèþ ïî óáûâàíèþ ñêàëÿðíîãî ïðîèçâåäåíèÿ èëè
êîñèíóñà óãëà. Äëÿ áèíàðíûõ âåêòîðîâ øèðîêî èñïîëüçóþò ðàññòîÿíèå Õýììèíãà
dist { }Ham ( , )a b � ���i
D
i ia b
1
, ãäå { }� — èíäèêàòîðíàÿ ôóíêöèÿ. Ñëîæíîñòü (âðå-
ìÿ) âû÷èñëåíèÿ ïðèâåäåííûõ ðàññòîÿíèé/ñõîäñòâ ñîñòàâëÿåò O D( ).
1.2. Òî÷íûé è ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó è òèïû çàïðîñîâ
1.2.1. Çàïðîñû òî÷íîãî ïîèñêà ïî ñõîäñòâó. Îáúåêòû áàçû, êîòîðûå ÿâëÿ-
þòñÿ îòâåòîì íà êîíêðåòíûé çàïðîñ ïîèñêà ïî ñõîäñòâó, îïðåäåëÿþòñÿ òèïîì çà-
ïðîñà è åãî ïàðàìåòðàìè (çàäàþòñÿ îáúåêòîì-çàïðîñîì, ìåðîé ðàññòîÿíèÿ/ñõîä-
ñòâà è äð.). Îáúåêòû-çàïðîñû ìîãóò íå ïðèíàäëåæàòü áàçå. Â íàñòîÿùåì îáçîðå
îáúåêòû ÿâëÿþòñÿ âåùåñòâåííûìè âåêòîðàìè.
Äèàïàçîííûé çàïðîñ (range query) îáîçíà÷èì rNN. Îí âîçâðàùàåò îáúåêòû
áàçû, ðàññòîÿíèÿ êîòîðûõ îò îáúåêòà-çàïðîñà (ïî ìåðå ðàññòîÿíèÿ, çàäàííîé â çà-
ïðîñå) íå ïðåâûøàþò ðàäèóñà çàïðîñà r. Ïðè íåêîòîðûõ r ðåçóëüòàòîì äèàïàçîííîãî
çàïðîñà ìîæåò ÿâëÿòüñÿ ïóñòîå ìíîæåñòâî îáúåêòîâ èëè âñå îáúåêòû êîíêðåòíîé
áàçû.  ïîñëåäíåì ñëó÷àå óñêîðåíèå âûïîëíåíèÿ çàïðîñà rNN ïî ñðàâíåíèþ ñ ëè-
íåéíûì ïîèñêîì íåâîçìîæíî â ïðèíöèïå. Ëþáîé îáúåêò, ÿâëÿþùèéñÿ îòâåòîì íà
äèàïàçîííûé çàïðîñ, íàçûâàþò r-áëèæíèì ñîñåäîì (near neighbor), îáîçíà÷èì åãî
rNN1. Çàïðîñ rNN1 âîçâðàùàåò òàêîé îáúåêò, åñëè îí èìååòñÿ â áàçå.
Çàïðîñ k áëèæàéøèõ ñîñåäåé (k nearest neighbors, kNN) âîçâðàùàåò k îáúåê-
òîâ áàçû, áëèæàéøèõ ê îáúåêòó-çàïðîñó. Çàïðîñ îäíîãî áëèæàéøåãî ñîñåäà,
à òàêæå îáúåêò, êîòîðûé ÿâëÿåòñÿ áëèæàéøèì ñîñåäîì, îáîçíà÷èì NN.
Çàïðîñû rNN è kNN ñ ïðèâåäåííûìè îïðåäåëåíèÿìè — çàïðîñû òî÷íîãî ïî-
èñêà ïî ñõîäñòâó. Îïðåäåëåíèÿ òèïîâ çàïðîñîâ â òåðìèíàõ íå ðàññòîÿíèÿ, à ñõîä-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 169
ñòâà àíàëîãè÷íû. Äðóãèå òèïû çàïðîñîâ òî÷íîãî ïîèñêà ïî ñõîäñòâó â íàñòîÿ-
ùåì îáçîðå íå ðàññìàòðèâàþòñÿ.
1.2.2. Ïðîáëåìû òî÷íîãî ïîèñêà è ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó.
Âðåìÿ âûïîëíåíèÿ çàïðîñîâ ïîèñêà ïî ñõîäñòâó ëèíåéíûì ïîèñêîì â áàçå èç N
îáúåêòîâ-âåêòîðîâ äëÿ ìåð ðàññòîÿíèÿ/ñõîäñòâà ñ âðåìåíåì âû÷èñëåíèÿ O D( )
ñîñòàâëÿåò O ND( ) .
Äëÿ äàííûõ ðàçìåðíîñòè D �1 (êàæäûé îáúåêò ïðåäñòàâëåí îäíèì ÷èñëîì)
íåñëîæíî áûñòðî âûïîëíÿòü òî÷íûå çàïðîñû ïîèñêà ïî ñõîäñòâó. Ñîðòèðóþò è
çàïîìèíàþò N ÷èñåë, ïðåäñòàâëÿþùèõ N îáúåêòîâ áàçû. Çàïðîñ NN âûïîëíÿþò
ïîèñêîì äèõîòîìèåé. Äëÿ òàêîé ÈÑ çàòðàòû ïàìÿòè ñîñòàâëÿþò O N( ), à âðåìÿ
ïîèñêà O N(log ) â õóäøåì ñëó÷àå [3].
Àíàëîãè÷íàÿ ÈÑ äëÿ D � 2 ñòðîèò äèàãðàììó Âîðîíîãî, ò.å. ðàçáèâàåò ïðî-
ñòðàíñòâà íà N îáëàñòåé, êàæäàÿ èõ êîòîðûõ ñîîòâåòñòâóåò îáúåêòó áàçû è ñîñòî-
èò èç òî÷åê ïðîñòðàíñòâà, êîòîðûå áëèæå ê íåìó, ÷åì ê äðóãèì îáúåêòàì áàçû.
Ê ñîæàëåíèþ, çàòðàòû ïàìÿòè íà õðàíåíèå äèàãðàììû Âîðîíîãî ñîñòàâëÿþò
O N
D
( )
/� �2
[10]. Ëó÷øèé èçâåñòíûé àëãîðèòì ýòîãî êëàññà äëÿ ïîèñêà NN, õîòÿ
è îáåñïå÷èâàåò âðåìÿ âûïîëíåíèÿ çàïðîñà O D NO( log )( )1 [11, 12], òðåáóåò N O D( )
ïàìÿòè, ÷òî íåðåàëüíî äëÿ áàç óìåðåííîãî ðàçìåðà N , äàæå ïðè ìàëûõ D . Äëÿ àë-
ãîðèòìîâ ñ çàòðàòàìè ïàìÿòè, áëèçêèìè ê ëèíåéíûì, âðåìÿ äëÿ ñëó÷àéíîãî îáúåê-
òà-çàïðîñà (â ñðåäíåì) min ( , )( )2O D DN [12]. Ïîýòîìó äëÿ áàç ñ äîñòèæèìûì N
òî÷íûé ïîèñê âûðîæäàåòñÿ â ëèíåéíûé, äàæå ïðè íå ñëèøêîì áîëüøèõ D , ÷òî
ïîäòâåðæäàåòñÿ è íà ïðàêòèêå [13].
Àíàëèç âñåõ èçâåñòíûõ àëãîðèòìîâ òî÷íîãî âûïîëíåíèÿ çàïðîñà NN ñ ñóá-
ëèíåéíûì îò N âðåìåíåì ïîêàçûâàåò, ÷òî çàòðàòû âðåìåíè èëè ïàìÿòè ðàñòóò
ýêñïîíåíöèàëüíî îò D [12]. Ñîãëàñíî ïðåäïîëîæåíèþ «ïðîêëÿòèÿ ðàçìåðíîñ-
òè» [12] òàêàÿ çàâèñèìîñòü íåèçáåæíà ïðè òî÷íîì ïîèñêå ïî ñõîäñòâó äëÿ äàí-
íûõ õóäøåãî ñëó÷àÿ (äëÿ îáúåêòîâ-çàïðîñîâ è îáúåêòîâ áàçû, êîòîðûå òðåáóþò
íàèáîëüøåãî âðåìåíè âûïîëíåíèÿ çàïðîñà). Äëÿ íåêîòîðûõ àëãîðèòìîâ ýêñïî-
íåíöèàëüíàÿ çàâèñèìîñòü ïðîÿâëÿåòñÿ â òåðìèíàõ «âíóòðåííåé ðàçìåðíîñòè»
(ñì. ññûëêè â [3]), êîòîðàÿ ìîæåò áûòü ìåíüøåé, ÷åì «âíåøíÿÿ» ðàçìåðíîñòü D .
Ïðåîäîëåòü (òî÷íåå, îáîéòè) ïðîêëÿòèå ðàçìåðíîñòè óäàåòñÿ ïåðåõîäîì îò
òî÷íîãî ê áîëåå áûñòðîìó, íî ïðèáëèæåííîìó ïîèñêó, äîïóñêàþùåìó îòëè÷èå
ðåçóëüòàòîâ îò òî÷íîãî ïîèñêà. Ðåäóêöèÿ ðÿäà äðóãèõ çàäà÷ ê çàäà÷å ïðèáëèæåí-
íîãî áëèæíåãî ñîñåäà îïèñàíà â [12].
1.2.3. Çàïðîñû ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó. Ïðèâåäåì ðàñïðîñòðà-
íåííûå òèïû çàïðîñîâ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó [14–16, 12].
Îáîçíà÷èì ( , )c � -rNN1 çàïðîñ âåðîÿòíîñòíîãî ñ-ïðèáëèæåííîãî r-áëèæíåãî
ñîñåäà (randomized ñ-approximate r-near neighbor); îí ñ âåðîÿòíîñòüþ, íå ìåíüøåé
1� �, âîçâðàùàåò ëþáîé îáúåêò áàçû ñ ðàññòîÿíèåì îò îáúåêòà-çàïðîñà, íå ïðåâû-
øàþùèì cr (c �1), åñëè ñóùåñòâóåò îáúåêò áàçû ñ ðàññòîÿíèåì îò îáúåêòà-çàïðî-
ñà, íå ïðåâûøàþùèì r. Åñëè òàêîãî îáúåêòà íå ñóùåñòâóåò, òî âîçâðàùàåòñÿ îáú-
åêò ñ ðàññòîÿíèåì, íå ïðåâûøàþùèì cr, èëè îòâåò «íåò».
Îáîçíà÷èì ( )c -rNN1 çàïðîñ ( , )c � -rNN1 ïðè � � 0 (äåòåðìèíèðîâàííûé âàðèàíò).
Îáîçíà÷èì ( )� -rNN âåðîÿòíîñòíûé äèàïàçîííûé çàïðîñ (all randomized r-near
neighbors); îí âîçâðàùàåò âñå îáúåêòû áàçû ñ ðàññòîÿíèåì îò îáúåêòà-çàïðîñà, íå
áîëüøèì r, ñ âåðîÿòíîñòüþ, íå ìåíüøåé 1� �, äëÿ êàæäîãî òàêîãî îáúåêòà.
Îáîçíà÷èì c-NN çàïðîñ ñ-ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà (approximate
nearest neighbor); îí âîçâðàùàåò îáúåêò áàçû, ðàññòîÿíèå êîòîðîãî îò îáúåêòà-çà-
ïðîñà íå áîëåå ÷åì â c �1ðàç ïðåâûøàåò ðàññòîÿíèå äî òî÷íîãî áëèæàéøåãî ñîñåäà.
Âûïîëíåíèå çàïðîñà c( )1� � -NN (äëÿ íåêîòîðîãî � � 0) ìîæíî ðåäóöèðî-
âàòü [16, 12] ê ïîñëåäîâàòåëüíîñòè çàïðîñîâ ( )c -rNN1 ñ ðàçëè÷íûìè ðàäèóñàìè.
Ïóñòü � — êîíå÷íîå îòíîøåíèå íàèáîëüøåãî è íàèìåíüøåãî ðàññòîÿíèé ìåæäó
îáúåêòàìè áàçû (âêëþ÷àÿ è çàïðîñ), ìèíèìàëüíîå ðàññòîÿíèå ðàâíî 1. Ïîñòðîèì
O (log )1� � � øòóê ÈÑ äëÿ ( )c -rNN1 ñ ðàäèóñàìè r, ïðèíèìàþùèìè çíà÷åíèÿ
170 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
0 5 1. ( )� � i äëÿ i � 0 1, ,� Ïðè ïîñòóïëåíèè çàïðîñà, âûïîëíèâ ïîèñê äèõîòîìèåé
â ýòèõ ÈÑ (ò.å. âûïîëíèâ O(log log )1� � � çàïðîñîâ ( )c -rNN1 ñ ðàçëè÷íûìè r),
íàéäåì îòâåò íà çàïðîñ c( )1� � -NN êàê îáúåêò, âîçâðàùåííûé ïðè ìèíèìàëüíîì
çíà÷åíèè r. Äëÿ ïðîèçâîëüíûõ ìåòðè÷åñêèõ ïðîñòðàíñòâ (ñ íåîãðàíè÷åííûì �)
â [16] ïðåäëîæåíà áîëåå ýôôåêòèâíàÿ (íî íåïðàêòè÷íàÿ) ðåäóêöèÿ íà îñíîâå ÈÑ
äëÿ çàïðîñà ( , )c � -rNN1. ×òîáû èçáåæàòü óâåëè÷åíèÿ çàòðàò ïàìÿòè, äëÿ ïîèñêà
ïðèáëèæåííîãî NN ÷àñòî èñïîëüçóþò äðóãèå ÈÑ, áåç ñïåöèôèöèðîâàííûõ òåî-
ðåòè÷åñêèõ ãàðàíòèé (êà÷åñòâî ïðîâåðÿþò íà áàçàõ).
Îòìåòèì, ÷òî îáîçíà÷åíèå NN â çàïðîñàõ ( )c -rNN1, ( , )c � -rNN1, ( )� -rNN èñ-
ïîëüçóåòñÿ äëÿ áëèæíåãî ñîñåäà, à â çàïðîñàõ NN, kNN, c-NN, c( )1� � -NN — äëÿ
áëèæàéøåãî ñîñåäà. Ïðàêòè÷åñêèå ÈÑ, âûïîëíÿþùèå íåêîòîðûå âåðîÿòíîñòíûå
çàïðîñû, îïèñàííûå â ýòîì ïîäðàçäåëå, ñ ãàðàíòèÿìè íà âðåìÿ âûïîëíåíèÿ äëÿ
äàííûõ õóäøåãî ñëó÷àÿ, ðàññìîòðåíû â ðàçä. 2.
1.2.4. Ìåðû êà÷åñòâà ïîèñêà ïî ñõîäñòâó. Ïðèáëèæåííûé ïîèñê ïî ñõîä-
ñòâó âîñòðåáîâàí íà ïðàêòèêå, ïîñêîëüêó äëÿ ìíîãèõ ïðèìåíåíèé äîñòàòî÷íî ïî-
ëó÷àòü ïðèáëèæåííûå ðåçóëüòàòû, íî áûñòðî.
Äëÿ àëãîðèòìîâ ïðèáëèæåííîãî ïîèñêà ñ êîëè÷åñòâåííûìè ãàðàíòèÿìè ðàñ-
ñìàòðèâàþò äâà òèïà îòëè÷èé èõ ðåçóëüòàòîâ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà.
 ñëó÷àå äåòåðìèíèðîâàííûõ ïðèáëèæåííûõ àëãîðèòìîâ ðàññòîÿíèå äî íàéäåí-
íûõ îáúåêòîâ íå áîëåå ÷åì íà çàäàííûé ìíîæèòåëü ïðåâûøàåò ðàññòîÿíèå äî îáú-
åêòîâ, êîòîðûå ÿâëÿþòñÿ òî÷íûì îòâåòîì íà çàïðîñ.  ñëó÷àå ðàíäîìèçèðîâàí-
íûõ àëãîðèòìîâ Monte Carlo äîïóñêàþòñÿ false negatives: àëãîðèòì ìîæåò íå âîç-
âðàòèòü îáúåêòû, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà çàïðîñ (îäíàêî âåðîÿòíîñòü ýòîãî
ïî ðåàëèçàöèÿì àëãîðèòìà è âðåìÿ ïîèñêà ïðè àíàëèçå îãðàíè÷èâàþò äëÿ äàííûõ
õóäøåãî ñëó÷àÿ). Àëãîðèòìû Monte Carlo, âûïîëíÿþùèå âåðîÿòíîñòíûå ïðèáëè-
æåííûå çàïðîñû, ìîãóò äàâàòü îáà îòëè÷èÿ. Ðàíäîìèçèðîâàííûå àëãîðèòìû Las
Vegas ðàáîòàþò áåç false negatives, ïðè àíàëèçå îãðàíè÷èâàþò ñðåäíåå ïî âñåì
ðåàëèçàöèÿì àëãîðèòìà âðåìÿ ïîèñêà äëÿ äàííûõ õóäøåãî ñëó÷àÿ (à íå äëÿ ñðåä-
íåãî, êàê óòâåðæäàëîñü â [4]).
Íà ïðàêòèêå ïîëüçîâàòåëåé ÷àñòî èíòåðåñóþò íå òåîðåòè÷åñêèå ãàðàíòèè, à âðå-
ìÿ âûïîëíåíèÿ çàïðîñîâ â ýêñïåðèìåíòàõ íà êîíêðåòíûõ áàçàõ. Ýòî âðåìÿ îáû÷íî
çàâèñèò îò âûáîðà ïàðàìåòðîâ ÈÑ. Äëÿ òî÷íîãî ïîèñêà ëó÷øåé ÿâëÿåòñÿ ÈÑ, îáåñ-
ïå÷èâàþùàÿ íàèìåíüøèå çàòðàòû âðåìåíè. Äëÿ ïðèáëèæåííîãî ïîèñêà âûáîð ïàðà-
ìåòðîâ ÈÑ îáû÷íî ïîçâîëÿåò äîñòè÷ü íåêîòîðîãî êîìïðîìèññà ìåæäó êà÷åñòâîì
ðåçóëüòàòîâ ïîèñêà (ñòåïåíüþ èõ îòëè÷èÿ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà) è âðåìå-
íåì ïîèñêà. Ïîýòîìó ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ñðàâíèâàþò ïî (óñðåäíåííîìó)
âðåìåíè âûïîëíåíèÿ çàïðîñà ïðè ôèêñèðîâàííîì êà÷åñòâå ïîèñêà èëè ïî çíà÷åíèþ
ìåðû êà÷åñòâà ïîèñêà ïðè îäèíàêîâîì âðåìåíè ïîèñêà. Âàæíîé õàðàêòåðèñòèêîé
òàêæå ÿâëÿþòñÿ çàòðàòû ïàìÿòè ÈÑ (êâàäðàòè÷íûå çàòðàòû íåïðèåìëåìû).
×àñòî èñïîëüçóþò ìåðû êà÷åñòâà âûïîëíåíèÿ êîíêðåòíîãî çàïðîñà, èçâåñ-
òíûå [17–19] êàê ïîëíîòà (recall), ðàâíàÿ n n1 2/ , è òî÷íîñòü (precision), ðàâíàÿ
n n1 3/ , ãäå n1 — êîëè÷åñòâî âîçðàùåííûõ îáúåêòîâ, ñîâïàâøèõ ñ ðåëåâàíòíûìè
çàïðîñó îáúåêòàìè â áàçå, n2 — êîëè÷åñòâî ðåëåâàíòíûõ çàïðîñó îáúåêòîâ â áàçå,
n3 — êîëè÷åñòâî âîçðàùåííûõ îáúåêòîâ áàçû. Äëÿ çàïðîñà kNN n n k2 3� � , ïîý-
òîìó òî÷íîñòü ðàâíà ïîëíîòå.  êà÷åñòâå ðåëåâàíòíûõ îáúåêòîâ èñïîëüçóþò îáú-
åêòû, âîçâðàùàåìûå çàïðîñàìè òî÷íîãî ïîèñêà ëèáî óêàçàííûå ýêñïåðòîì. «Õîðî-
øèìè» ñîñåäÿìè ìîãóò áûòü íå òîëüêî òî÷íûå ñîñåäè, íî è îáúåêòû áàçû, áëèçêèå
ê òî÷íûì ñîñåäÿì. Ïîýòîìó êà÷åñòâî ïîèñêà òàêæå èçìåðÿþò îòíîøåíèåì ñóììû
(èëè ñðåäíåãî) ðàññòîÿíèé îáúåêòà-çàïðîñà äî âîçâðàùåííûõ îáúåêòîâ ê ñîîòâåò-
ñòâóþùåé âåëè÷èíå äëÿ ýòàëîííîãî ðåçóëüòàòà (distance ratio metric) è äð. [19].
Ïðè âûïîëíåíèè ìíîæåñòâà çàïðîñîâ ïîëó÷åííûå äëÿ èíäèâèäóàëüíûõ çàïðîñîâ
çíà÷åíèÿ ìåð êà÷åñòâà óñðåäíÿþò. Òàê, äëÿ çàïðîñà NN ïîëíîòó (ðàâíóþ òî÷íîñòè)
èçìåðÿþò êàê ïðîöåíò çàïðîñîâ, äëÿ êîòîðûõ áûë âîçâðàùåí ýòàëîííûé NN [20].
1.3. Îáùèå ïðèíöèïû êîíñòðóèðîâàíèÿ è ïðèìåíåíèÿ èíäåêñíûõ
ñòðóêòóð.  îáåèõ ÷àñòÿõ îáçîðà (÷àñòü II ãîòîâèòñÿ ê ïóáëèêàöèè) ðàññìàòðèâà-
þòñÿ â îñíîâíîì ÈÑ, ïðè ïîñòðîåíèè êîòîðûõ íåêîòîðûì îáðàçîì ðàçáèâàþò
ìíîæåñòâî îáúåêòîâ áàçû íà ïîäìíîæåñòâà (â îäíèõ òèïàõ ÈÑ îíè íå ïåðåñåêà-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 171
þòñÿ, à â äðóãèõ èõ ïåðåñå÷åíèå âîçìîæíî). Íåêîòîðûå òèïû ÈÑ õðàíÿò è èñ-
ïîëüçóþò èíôîðìàöèþ îá îáëàñòÿõ ïðîñòðàíñòâà îáúåêòîâ, êîòîðûì ïðèíàäëå-
æàò ýòè ïîäìíîæåñòâà. Èíîãäà äëÿ îäíîé áàçû êîíñòðóèðóþò íåñêîëüêî ÈÑ
ñ ðàçëè÷íûìè ðàçáèåíèÿìè íà ïîäìíîæåñòâà.
Ðàçëè÷àþò ñòàòè÷åñêèå è äèíàìè÷åñêèå ÈÑ.  ñòàòè÷åñêèõ àëãîðèòì êîíñòðóè-
ðîâàíèÿ ÈÑ ïðåäïîëàãàåò íàëè÷èå âñåé áàçû îáúåêòîâ.  äèíàìè÷åñêèõ êîíñòðóèðî-
âàíèå îñóùåñòâëÿåòñÿ îïåðàöèÿìè âñòàâêè îáúåêòîâ ïî ìåðå ïîñòóïëåíèÿ äàííûõ.
Ïðè âûïîëíåíèè çàïðîñà ïðèìåíÿþò ïðîöåäóðû, êîòîðûå ìîæíî ñ÷èòàòü âàðè-
àíòàìè äâóõýòàïíîé ñòðàòåãèè ôèëüòðàöèè è óòî÷íåíèÿ (filter-and-refine, F&R). Íà
ïåðâîì ýòàïå îñóùåñòâëÿþò áûñòðûé îòáîð îáúåêòîâ-êàíäèäàòîâ. Ðåçóëüòàòû ïåð-
âîãî ýòàïà óòî÷íÿþòñÿ íà âòîðîì ýòàïå (îáû÷íî ñ èñïîëüçîâàíèåì ëèíåéíîãî ïîèñ-
êà ñðåäè îáúåêòîâ-êàíäèäàòîâ ïî ìåðå ðàññòîÿíèÿ/ñõîäñòâà, çàäàííîé â çàïðîñå).
Ñòðàòåãèþ F&R èíîãäà ïðèìåíÿþò ìíîãîêðàòíî ïðè âûïîëíåíèè îäíîãî çàïðîñà.
Åñëè ñóììàðíîå êîëè÷åñòâî îáúåêòîâ–êàíäèäàòîâ ìåíüøå êîëè÷åñòâà îáúåêòîâ
áàçû N è èõ îòáîð âûïîëíÿåòñÿ äîñòàòî÷íî áûñòðî, ìîæíî ïîëó÷èòü óñêîðåíèå âû-
ïîëíåíèÿ çàïðîñà îòíîñèòåëüíî ëèíåéíîãî ïîèñêà (ñóáëèíåéíûé ïîèñê).
Äëÿ òî÷íîãî ïîèñêà ïðè âûïîëíåíèè çàïðîñà êàíäèäàòû âûáèðàþòñÿ òàê, ÷òî
îíè ãàðàíòèðîâàííî ñîäåðæàò îòâåò íà çàïðîñ òî÷íîãî ïîèñêà. Ìíîãèå ÈÑ òî÷íîãî
ïîèñêà ïî ñõîäñòâó èñïîëüçóþò ðàçíîâèäíîñòè ìåòîäà âåòâåé è ãðàíèö (branch and
bound, B&B) (ñì. îáçîð [3]). Îäíàêî cóáëèíåéíîå âðåìÿ âûïîëíåíèÿ çàïðîñîâ òî÷-
íîãî ïîèñêà íå ãàðàíòèðóåòñÿ è íå íàáëþäàåòñÿ íà ïðàêòèêå (ïîäðàçä. 1.2.2).
 áàçîâîì âàðèàíòå ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó íà îñíîâå ñîõðà-
íÿþùåãî ñõîäñòâî õýøèðîâàíèÿ ñòàâÿò â ñîîòâåòñòâèå îáúåêòàì òàêèå õýø-çíà÷åíèÿ,
÷òî âåðîÿòíîñòü ñîâïàäåíèÿ õýøåé ñõîäíûõ îáúåêòîâ âûøå, ÷åì íåñõîäíûõ. Îáúåêòû
ñ îäèíàêîâûì çíà÷åíèåì õýøåé îáðàçóþò ïîäìíîæåñòâà â ÈÑ. Ïðè âûïîëíåíèè çà-
ïðîñà îáúåêòàìè-êàíäèäàòàìè ÿâëÿþòñÿ ïîäìíîæåñòâà ñ òåì æå çíà÷åíèåì õýøà, ÷òî
è îáúåêò-çàïðîñ. Ýòî îáåñïå÷èâàåò èçâëå÷åíèå îáúåêòîâ-êàíäèäàòîâ, ñõîäíûõ ñ îáú-
åêòîì-çàïðîñîì, è ãàðàíòèðóåò ñóáëèíåéíîå âðåìÿ âûïîëíåíèÿ íåêîòîðûõ òèïîâ çà-
ïðîñîâ âåðîÿòíîñòíîãî ïðèáëèæåííîãî ïîèñêà (â ÷àñòíîñòè ( , )c � -rNN1).
2. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÍÀ ÎÑÍÎÂÅ ÑÎÕÐÀÍßÞÙÅÃÎ
ÑÕÎÄÑÒÂÎ ÕÝØÈÐÎÂÀÍÈß
 ëîêàëüíî-÷óâñòâèòåëüíîì õýøèðîâàíèè (LSH), â îòëè÷èå îò îáû÷íîãî, LSH-
ôóíêöèè ãåíåðèðóþò õýø-çíà÷åíèÿ òàê, ÷òî âåðîÿòíîñòü èõ ñîâïàäåíèÿ ó ñõîäíûõ
îáúåêòîâ âûøå, ÷åì ó íåñõîäíûõ ([15, 16], îáçîðû [2] è [4]). Îáúåêòû ñ îäèíàêî-
âûì õýøåì îáðàçóþò êîðçèíó. Ïðè ïîñòóïëåíèè îáúåêòà-çàïðîñà ãåíåðèðóþò åãî
LSH-õýø, èçâëåêàþò èç ñîîòâåòñòâóþùåé êîðçèíû îáúåêòû áàçû è èñïîëüçóþò
èõ â êà÷åñòâå êàíäèäàòîâ äëÿ ëèíåéíîãî ïîèñêà ïî èñõîäíîìó ðàññòîÿíèþ.
Õýø-çíà÷åíèÿ ñõîäíûõ îáúåêòîâ, ñãåíåðèðîâàííûå îäíîé LSH-ôóíêöèåé, ìîãóò
îêàçàòüñÿ ðàçëè÷íûìè, ïîýòîìó äëÿ ïîâûøåíèÿ âåðîÿòíîñòè íàõîæäåíèÿ áëèçêèõ
ê çàïðîñó îáúåêòîâ îáúåäèíÿþò ñïèñêè êàíäèäàòîâ èç êîðçèí íåñêîëüêî íåçàâèñè-
ìûõ LSH-ôóíêöèé, àíàëîãè÷íî ëåñàì äåðåâüåâ (ñì., íàïðèìåð, [20]). Èíäåêñíûå
ñòðóêòóðû íà îñíîâå LSH — îäíè èç íåìíîãèõ ðåàëèçîâàííûõ ïðàêòè÷åñêè äëÿ
íåêîòîðûõ òèïîâ çàïðîñîâ ïðèáëèæåííîãî âåðîÿòíîñòíîãî ïîèñêà ïî ñõîäñòâó
ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè â õóäøåì ñëó÷àå.
2.1. Èíäåêñíàÿ ñòðóêòóðà LSH äëÿ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó
2.1.1. LSH-ôóíêöèè. Ñåìåéñòâî F õýø-ôóíêöèé h ÿâëÿåòñÿ ( , , , )r r p p1 2 1 2 -÷óâ-
ñòâèòåëüíûì äëÿ ëþáûõ îáúåêòîâ a b, ïðè âûïîëíåíèè óñëîâèé: åñëè dist ( , )a b r� 1,
òî Pr { }F h a h b p( ) ( )� � 1, à åñëè dist ( , )a b r� 2 , òî Pr { }F h a h b p( ) ( )� � 2 [15, 16], ãäå
âåðîÿòíîñòü Pr ñîîòâåòñòâóåò ñëó÷àéíîìó ðàâíîìåðíîìó âûáîðó õýø-ôóíêöèé h èç
ñåìåéñòâà. Äëÿ ïîëåçíîãî LSH-ñåìåéñòâà r r1 2
è p p1 2� . Ýòî îïðåäåëåíèå LSH —
íà îñíîâå çàçîðà ðàññòîÿíèé ìåæäó ñõîäíûìè è íåñõîäíûìè îáúåêòàìè.
Àíàëîãè÷íî ìîæíî äàòü îïðåäåëåíèå LSH íà îñíîâå çàçîðà ñõîäñòâ [21].
 äðóãîì îïðåäåëåíèè LSH íà îñíîâå ìîíîòîííîñòè âåëè÷èíû ñõîäñòâà [22]
äëÿ LSH-ôóíêöèé äîëæíî âûïîëíÿòüñÿ Pr { } simF h a h b a b( ) ( ) ( , )� � , ãäå sim —
ìåðà ñõîäñòâà îáúåêòîâ, ïðèíèìàþùàÿ çíà÷åíèÿ â [ , ]0 1 . Îòìåòèì, ÷òî sim ìîæåò
òàêæå ÿâëÿòüñÿ ìîíîòîííî âîçðàñòàþùåé ôóíêöèåé ñî çíà÷åíèÿìè â [ , ]0 1 îò íå-
êîòîðîé äðóãîé ôóíêöèè ñõîäñòâà [21]. Àíàëîãè÷íîå îïðåäåëåíèå ñóùåñòâóåò è
172 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
äëÿ ðàññòîÿíèé. Èç îïðåäåëåíèÿ LSH íà îñíîâå ìîíîòîííîñòè ñëåäóåò îïðåäåëå-
íèå íà îñíîâå çàçîðà [21]. Îòìåòèì îáîáùåíèå LSH âèäà Pr { }F h a h b1 2( ) ( )� �
� f a b( ( , ))dist , ãäå f ( ) ìîæåò íå ÿâëÿòüñÿ óáûâàþùåé ôóíêöèåé dist [23].
Ïðèìåð LSH-ôóíêöèè. Äëÿ óãëà � ìåæäó âåêòîðàìè øèðîêî ïðèìåíÿåòñÿ ñåìåé-
ñòâî LSH-ôóíêöèé SimHash [22]: hr a r a( ) ( , )� � �sign , r — ñëó÷àéíûé âåêòîð ðàçìåð-
íîñòè D ñ êîìïîíåíòàìè, êîòîðûå ÿâëÿþòñÿ íåçàâèñèìî è îäèíàêîâî ðàñïðåäåëåííûìè
(i.i.d.) ñëó÷àéíûìè âåëè÷èíàìè (ñ.â.) èç ãàóññîâà ðàñïðåäåëåíèÿ ( ~ ( , )r 0 INorm D ),
sign(z) �1 ïðè z � 0 è sign(z) � �1 ïðè z
0. Äëÿ ýòîé LSH-ôóíêöèè
Pr { )}h h( ) ( ( , ) /a b a b� � �1 � �. Äðóãèå ïðèìåðû LSH ðàññìîòðåíû â ïîäðàçä. 2.2.
2.1.2. Áàçîâàÿ èíäåêñíàÿ ñòðóêòóðà LSH. Ïðè êîíñòðóèðîâàíèè ÈÑ íà
îñíîâå LSH ñîçäàþò è çàïîìèíàþò L LSH-ôóíêöèé g, êàæäàÿ èç êîòîðûõ ÿâëÿåò-
ñÿ êîíêàòåíàöèåé m LSH-ôóíêöèé h, ñëó÷àéíî âûáðàííûõ èç ñåìåéñòâà LSH.
Ôóíêöèÿ g ÿâëÿåòñÿ ( , , , )r r p pm m
1 2 1 2
-÷óâñòâèòåëüíîé. (Ïðè àíàëèçå çàïðîñà
( , )c � -rNN1 ïîëàãàþò r r1 � , r cr2 � .) Äëÿ êàæäîé èç L ôóíêöèé g êîíñòðóèðóþò
ñâîþ õýø-òàáëèöó. Êàæäûé îáúåêò áàçû y ïîìåùàþò â îäíó êîðçèíó êàæäîé èç
L õýø-òàáëèö (êîðçèíó, êîòîðàÿ ñîîòâåòñòâóåò åãî õýøó g y( ) äëÿ ýòîé òàáëèöû).
Òàêèì îáðàçîì, îáúåêòû ñ îäèíàêîâûìè çíà÷åíèÿìè g ïîïàäàþò â îäíó êîðçèíó.
Òàê êàê ïðè N m
2 áîëüøèíñòâî ÿ÷ååê òàáëèö ïóñòû, ê LSH-õýøàì äîïîëíè-
òåëüíî ïðèìåíÿþò îáû÷íîå õýøèðîâàíèå. Äðóãèå îñîáåííîñòè ðåàëèçàöèè áàçî-
âîé ÈÑ LSH îïèñàíû â [24].
Äëÿ âûïîëíåíèÿ çàïðîñà â ÈÑ LSH èñïîëüçóþò ñòðàòåãèþ F&R. Õýøè îáúåê-
òà-çàïðîñà ãåíåðèðóþò òåìè æå LSH-ôóíêöèÿìè, ÷òî ïðèìåíÿëèñü äëÿ êîíñòðóèðî-
âàíèÿ ÈÑ. Îáúåêòû-êàíäèäàòû èçâëåêàþò èç êîðçèí, õýøè êîòîðûõ ñîâïàäàþò ñ õý-
øàìè îáúåêòà-çàïðîñà (êîëëèçèÿ). Äëÿ âûïîëíåíèÿ çàïðîñà ( , )c � -rNN1 âûáèðàþò
ôèêñèðîâàííîå ÷èñëî îáúåêòîâ èç ýòèõ êîðçèí, íàïðèìåð 3L, âêëþ÷àÿ äóáëèêàòû
(«Ñòðàòåãèÿ 1» [15]). Äëÿ çàïðîñà ( )� -rNN èñïîëüçóþò âñå îáúåêòû èç ýòèõ êîðçèí
(«Ñòðàòåãèÿ 2» [15]). Îêîí÷àòåëüíûé ðåçóëüòàò ïîëó÷àþò ëèíåéíûì ïîèñêîì
â ñïèñêå êàíäèäàòîâ ïî ìåðå ðàññòîÿíèÿ/ñõîäñòâà çàïðîñà.
Èñïîëüçóÿ � � � �log / / log / log / log ( , )1 1 0 11 2 1 2p p p p , ìîæíî çàïèñàòü
L N� � . Ïîëó÷àåì çàòðàòû ïàìÿòè íà LSH-ñòðóêòóðó èç L òàáëèö è áàçó
O DN N( )� �1 � . Âðåìÿ ïîèñêà ñîñòîèò èç âðåìåíè âû÷èñëåíèÿ õýø-ôóíêöèé
O Lm O N N( ) ( log )� � è âðåìåíè âû÷èñëåíèÿ ðàññòîÿíèé äî êàíäèäàòîâ
O LD O N D( ) ( )� � . Ñòðàòåãèÿ 1 ãàðàíòèðóåò âðåìÿ ïîèñêà, òàê êàê êîëè÷åñòâî
êàíäèäàòîâ îãðàíè÷åíî. Òàêèì îáðàçîì, �
1 (÷óâñòâèòåëüíîñòü) õàðàêòåðèçóåò
«êà÷åñòâî» LSH-ôóíêöèé (íàñêîëüêî îíè ïîçâîëÿþò óñêîðèòü ïîèñê îòíîñèòåëü-
íî ëèíåéíîãî, êàêîâû çàòðàòû ïàìÿòè). Îáû÷íî � �1äëÿ c �1è � � 0 äëÿ c � � .
Ïðè ðàñ÷åòå ïàðàìåòðîâ äëÿ ñòðàòåãèè 2 (çàïðîñ ( )� -rNN) âûáèðàþò [24]
L pm� �� �log / log( )� 1
1
, à çíà÷åíèå m, ìèíèìèçèðóþùåå âðåìÿ çàïðîñà, îïðåäå-
ëÿþò â ýêñïåðèìåíòàõ. Â [25] âûáèðàþò L, èñõîäÿ èç èìåþùåéñÿ ïàìÿòè,
à m pL� �� �log( ) / log/1 1
1� .
2.2. Ïðèìåðû LSH-ôóíêöèé. Ðàñ÷åò ÈÑ LSH äëÿ êîíêðåòíîé ìåðû ðàññòî-
ÿíèÿ/ñõîäñòâà òðåáóåò íàëè÷èÿ äëÿ íåå LSH-ñåìåéñòâà (ñ èçâåñòíûìè õàðàêòå-
ðèñòèêàìè, êîòîðûå íå çàâèñÿò îò êîíêðåòíîãî íàáîðà îáúåêòîâ áàçû). Àðñåíàë
LSH-ñåìåéñòâ ñì. â îáçîðàõ [15, 26, 2, 27]. Áîëüøèíñòâî LSH-ñåìåéñòâ ðàçðàáî-
òàíî äëÿ âåêòîðîâ (íî ñì. [28, 29] äëÿ ÿäåðíûõ ñõîäñòâ).
Äëÿ ïðîñòðàíñòâ Ls, s�( , ]0 2 , ïðåäëîæåíû ñåìåéñòâà LSH [24] ñ èñïîëüçîâà-
íèåì âåêòîðîâ r ñ êîìïîíåíòàìè — i.i.d. ñ.â. èç s-óñòîé÷èâûõ ðàñïðåäåëåíèé:
h U w( ) ( , ) /a r a� � � �� � , ãäå w — ïàðàìåòð, îïðåäåëÿþùèé ðàçìåð õýø-êîðçèíû,
U — i.i.d. ñ.â. èç ðàâíîìåðíîãî ðàñïðåäåëåíèÿ â [ , ]0 w : U w~ , )Unif (0 . Ïðèìåðà-
ìè s-óñòîé÷èâûõ ðàñïðåäåëåíèé ÿâëÿþòñÿ: ðàñïðåäåëåíèå Êîøè äëÿ s �1 è Ãàóñ-
ñà äëÿ s � 2. Äëÿ ýòèõ ñåìåéñòâ � � �max / , / ( ){ }1 1 1c c os . Îáîçíà÷èì LSH-ôóíê-
öèè ýòîãî ñåìåéñòâà L2LSH äëÿ L2 è L1LSH äëÿ L1.
 [30] äëÿ L2 ïîëó÷åíî � � �1 12/ ( )c o , ÷òî ÿâëÿåòñÿ îïòèìàëüíûì çíà÷åíè-
åì. Âíà÷àëå âûïîëíÿþò ñëó÷àéíîå ïðîåöèðîâàíèå (ñì. îáçîð [1]) èñõîäíûõ âåê-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 173
òîðîâ â âåêòîðû ñíèæåííîé ðàçìåðíîñòè, çàòåì âûáèðàþò ìíîæåñòâî ñëó÷àéíûõ
âåêòîðîâ. Çíà÷åíèåì LSH-õýøà ÿâëÿåòñÿ èäåíòèôèêàòîð ïåðâîãî ñëó÷àéíîãî âåê-
òîðà, øàðó âîêðóã êîòîðîãî ñ çàäàííûì ðàäèóñîì ïðèíàäëåæèò õýøèðóåìûé âåê-
òîð.  áîëåå ïðàêòè÷åñêèõ âàðèàíòàõ õýø-çíà÷åíèåì ÿâëÿåòñÿ áëèæàéøàÿ òî÷êà
ðåøåòêè [30, 31].
×òîáû ðàññòîÿíèå èìåëî ñåìåéñòâî LSH-ôóíêöèé, íåîáõîäèìî (íî íå äîñòà-
òî÷íî) ÷òîáû îíî áûëî ìåòðè÷åñêèì [22] è èìåëî èçîìåòðè÷åñêîå âëîæåíèå
â L1 [32]. Åñëè êàæäîå èç äâóõ ñõîäñòâ èìååò LSH-ôóíêöèþ, èõ ïðîèçâåäåíèå
òàêæå åå èìååò. Íåîáõîäèìûì è äîñòàòî÷íûì óñëîâèåì ñîõðàíåíèÿ ñâîéñòâà
LSH äëÿ ôóíêöèè ïðåîáðàçîâàíèÿ ñõîäñòâà ÿâëÿåòñÿ åå ïðèíàäëåæíîñòü ê êëàññó
(ìàñøòàáèðîâàííûõ) ïðîèçâîäÿùèõ ôóíêöèé âåðîÿòíîñòåé. Â [33] ðàññìàòðèâà-
þò ñõîäñòâà, êîòîðûå íå èìåþò LSH, è ââîäÿò ïîíÿòèå èñêàæåíèÿ, ÷òîáû îõàðàê-
òåðèçîâàòü àïïðîêñèìàöèþ òàêèõ ñõîäñòâ òåìè, ÷òî èìåþò LSH. Ïîêàçàíû ïëîò-
íûå âåðõíèå è íèæíèå ãðàíèöû èñêàæåíèÿ äëÿ èçâåñòíûõ ñõîäñòâ áåç LSH, ïîä-
òâåðæäåííûå ýêñïåðèìåíòàìè.
Îòìåòèì, ÷òî íàëè÷èå LSH-ñåìåéñòâ äëÿ L1 â ïðèíöèïå ïîçâîëÿåò èñïîëüçîâàòü
ÈÑ LSH äëÿ ïðèáëèæåííîãî ïîèñêà ïî ïðåäñòàâëåíèÿì îáúåêòîâ è èõ ðàññòîÿíèÿì,
êîòîðûå ìîæíî ïðåîáðàçîâàòü â L1 c íåêîòîðûì èñêàæåíèåì (íàïðèìåð, ðàññòîÿíèå
ðåäàêòèðîâàíèÿ, áóëüäîçåðà è äð. [34, 16, 35, 1]). Âîçìîæíî ïðèìåíåíèå LSH-ôóíê-
öèè è äëÿ ôîðìèðîâàíèÿ áèíàðíûõ èëè öåëî÷èñëåííûõ êîìïîíåíòîâ âåêòîðîâ
(ñêåò÷åé) äëÿ îöåíêè ñîîòâåòñòâóþùèõ LSH-ôóíêöèÿì ðàññòîÿíèé/ñõîäñòâ ìåæäó
èñõîäíûìè îáúåêòàìè ïî ýìïèðè÷åñêîé âåðîÿòíîñòè ñîâïàäåíèÿ õýøåé (dist Ham / D
ñêåò÷åé [2]) ñîãëàñíî îïðåäåëåíèþ LSH íà îñíîâå ìîíîòîííîñòè.
 êà÷åñòâå ïðèìåðà LSH ðàññìîòðèì íåäàâíî ïîÿâèâøèåñÿ LSH-ôóíêöèè
äëÿ åäèíè÷íîé ñôåðû.
2.2.1. LSH-ôóíêöèè è ðåàëèçàöèÿ ïîèñêà ïî åâêëèäîâó ðàññòîÿíèþ åäè-
íè÷íûõ âåêòîðîâ. Îïòèìàëüíîå è ýôôåêòèâíî ðåàëèçóåìîå ñåìåéñòâî LSH-
ôóíêöèé äëÿ åâêëèäîâà ðàññòîÿíèÿ âåêòîðîâ íà åäèíè÷íîé ñôåðå ïðîàíàëèçèðî-
âàíî â [36]. Èç ñîîòíîøåíèé, ïðèâåäåííûõ â ïîäðàçä. 1.1, ñëåäóåò åãî ïðèìåíè-
ìîñòü äëÿ ïîèñêà ïî íåêîòîðûì äðóãèì ìåðàì. Ñåìåéñòâî èñïîëüçóåò ñëó÷àéíî
ïîâåðíóòûå ãèïåðîêòàýäðû (åäèíè÷íûå øàðû â L1) [37, 38]. Äëÿ ïîëó÷åíèÿ çíà-
÷åíèÿ LSH-õýøà âåêòîðà åãî óìíîæàþò íà ñëó÷àéíóþ i.i.d. ãàóññîâó ìàòðèöó
R D D( )� , ñâîþ äëÿ êàæäîé LSH-ôóíêöèè, ðåçóëüòàò íîðìèðóþò ê åäèíè÷íîé
íîðìå. Çàòåì íàõîäÿò áëèæàéøóþ ê ïîëó÷åííîìó âåêòîðó âåðøèíó ãèïåðîêòàýä-
ðà (ìàêñèìàëüíûé êîìïîíåíò âåêòîðà), íîìåð êîòîðîé è ÿâëÿåòñÿ õýø-çíà÷åíè-
åì. Ýòî âû÷èñëèòåëüíî ýôôåêòèâíî, òàê êàê ðàññòîÿíèå ýêâèâàëåíòíî ñêàëÿðíî-
ìó ïðîèçâåäåíèþ, à â âåêòîðàõ âåðøèí íåíóëåâîé òîëüêî îäèí êîìïîíåíò.
Äëÿ ïîëíîãî äèàïàçîíà ðàññòîÿíèé 0 2
r cr ïîëó÷åíà çàâèñèìîñòü
� � � � �( / )( ) / ( ) ( )1 4 4 12 2 2 2c c r r o , ãäå o ( )1 0� ïðè D � � . Ïðè r c� 2 / ,
rc � 2 ýòà LSH äîñòèãàåò îïòèìàëüíîãî çíà÷åíèÿ � � �1 2 12/ ( )c , êàê è çàâèñÿ-
ùèå îò äàííûõ LSH äëÿ L2 [39] (êîòîðûå, îäíàêî, ïðàêòè÷åñêè íå ðåàëèçóåìû
âñëåäñòâèå áîëüøîãî âðåìåíè âû÷èñëåíèÿ, ïîäðàçä. 2.6.3). Äàíà òàêæå íèæíÿÿ
ãðàíèöà � äëÿ ðàçëè÷íûõ ñîîòíîøåíèé p p1 2, , êîòîðàÿ ïîêàçûâàåò, ÷òî
ãèïåðîêòàýäðíûé LSH áëèçîê ê îïòèìàëüíîìó.
Äëÿ óñêîðåíèÿ õýøèðîâàíèÿ (áåç òåîðåòè÷åñêèõ ãàðàíòèé) [36] èñïîëüçóþò
hashing trick ñíèæåíèÿ ðàçìåðíîñòè è áûñòðîå óìíîæåíèå íà îðòîãîíàëüíûé ìàò-
ðè÷íûé êîíâåéåð (ñì. îáçîð [1]), à òàêæå ñïåöèàëèçèðîâàííûé ìóëüòèïðîáíûé
LSH (ïîäðàçä. 2.3.1). Ïðîãðàììíàÿ ðåàëèçàöèÿ FALCONN óñêîðÿåò çàïðîñ NN íà
ðÿäå áàç ïî ñðàâíåíèþ ñ SimHash â 4–10 ðàç äëÿ áîëüøèõ N [36] (õîòÿ ïîëó÷åíèå
çíà÷åíèÿ õýøà òðåáóåò áîëüøåãî âðåìåíè). Îòìåòèì, îäíàêî, ÷òî äëÿ SimHash òàê-
æå âîçìîæíî óñêîðåíèå ïðèìåíåíèåì áûñòðûõ ìàòðè÷íûõ êîíâåéåðîâ [2].
 [40] èññëåäîâàí ãèïåðêóáè÷åñêèé LSH, ãäå ðàçáèåíèå íà îáëàñòè ïðîèçâîäèòñÿ
îðòîãîíàëüíûìè ãèïåðïëîñêîñòÿìè (îáëàñòÿìè Âîðîíîãî âîêðóã âåðøèí ãèïåðêóáà).
Ïðåäâàðèòåëüíî âûïîëíÿåòñÿ ñëó÷àéíîå âðàùåíèå õýøèðóåìîãî âåêòîðà (äëÿ áûñòðî-
ãî ïñåâäîñëó÷àéíîãî âðàùåíèÿ òàêæå ìîæíî ïîëó÷èòü òåîðåòè÷åñêèå ãàðàíòèè [41]).
Äëÿ ãèïåðêóáè÷åñêîãî LSH � íàõîäèòñÿ ìåæäó SimHash è ãèïåðîêòàýäðíûì, îäíàêî
íåêîòîðûå ïðèìåíåíèÿ ðàáîòàþò áûñòðåå ñ ãèïåðêóáè÷åñêèì LSH [40].
174 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
2.3. Óëó÷øåíèÿ áàçîâîé ÈÑ LSH
2.3.1. Ìóëüòèïðîáíûé LSH. Áîëüøîå êîëè÷åñòâî L òàáëèö LSH òðåáóåò çíà-
÷èòåëüíûõ çàòðàò ïàìÿòè. Äëÿ óìåíüøåíèÿ L (ñ ñîõðàíåíèåì êà÷åñòâà ïîèñêà)
â [42, 43] ïðåäëîæåíî èçìåíèòü ïðîöåäóðó âûïîëíåíèÿ çàïðîñà òàê, ÷òîáû èçâëå-
êàòü êàíäèäàòîâ íå òîëüêî èç îäíîé êîðçèíû òàáëèöû, ñîîòâåòñòâóþùåé LSH-õýøó
çàïðîñà, íî è èç äðóãèõ êîðçèí, «áëèçêèõ» ê îáúåêòó-çàïðîñó. Â òàêîì «ìóëüòèïðîá-
íîì» (multi-probe) LSH èñïîëüçóþò êàê ìîäèôèêàöèè âåêòîðà çàïðîñà [42], òàê è
(áîëåå áûñòðûå) ìîäèôèêàöèè LSH-õýøà çàïðîñà [43]. Ñõåìó ãåíåðàöèè ìîäèôèêà-
öèé è ïîðÿäêà îáõîäà êîðçèí êîíñòðóèðóþò òàê, ÷òîáû îíà áûëà âû÷èñëèòåëüíî ýô-
ôåêòèâíîé è â ïåðâóþ î÷åðåäü îáåñïå÷èâàëà ïîñåùåíèå íàèáîëåå «ïåðñïåêòèâíûõ»
êîðçèí äëÿ êîíêðåòíîãî îáúåêòà-çàïðîñà.  [43] ïîëó÷åíû òàêèå æå òî÷íîñòü è âðå-
ìÿ çàïðîñà kNN, êàê è ó áàçîâîãî LSH, ïðè óìåíüøåíèè L áîëåå ÷åì â 10 ðàç.
Ýêñïåðèìåíòàëüíûå èññëåäîâàíèÿ âàðèàíòîâ ìîäèôèêàöèè õýø-êîäà çàïðî-
ñà [44, 45] ïîêàçàëè õîðîøèå ðåçóëüòàòû. Â ýêñïåðèìåíòàõ [36] ïî ïîèñêó (òî÷-
íîãî) NN ïðè îäèíàêîâûõ 1� � è L âðåìÿ çàïðîñà äëÿ ìóëüòèïðîáíîãî âàðèàíòà
óìåíüøèëîñü áîëåå ÷åì â 10 ðàç (çà ñ÷åò áîëüøåãî îïòèìàëüíîãî çíà÷åíèÿ m,
îáåñïå÷èâàþùåãî ìåíüøåå êîëè÷åñòâî êàíäèäàòîâ).
Ìóëüòèïðîáíûé LSH èñïîëüçóåòñÿ òàêæå â òåîðåòè÷åñêèõ ðàáîòàõ.  [46]
åãî ïðèìåíÿþò äëÿ ïîëó÷åíèÿ ïëàâíîãî êîìïðîìèññà ìåæäó çàòðàòàìè ïàìÿòè è
âðåìåíåì ïîèñêà. Äëÿ ìóëüòèïðîáíîãî âàðèàíòà àäàïòèâíîé ÈÑ LSH [47] (è ïîä-
ðàçä. 2.3.3) äëÿ çàïðîñà ( )� -rNN òåîðåòè÷åñêè îáîñíîâàíà íå òîëüêî ýêîíîìèÿ
ïàìÿòè, íî è óñêîðåíèå âûïîëíåíèÿ çàïðîñà.
Äëÿ çàïðîñà rNN (áåç false negatives) â Ls, s� �[ , ]1 , ïðåäëîæåíî [48] ñåìåé-
ñòâî LSH-ôóíêöèé âèäà h rDs
s( ) , / ( )– /x x r� � �� �1 1 , ãäå r — ðàäèóñ çàïðîñà, r —
âåêòîð i.i.d. ñ.â. èç îãðàíè÷åííîãî öåíòðèðîâàííîãî ðàñïðåäåëåíèÿ: � � �1 1ri ,
E{ }ri � 0.  êà÷åñòâå êàíäèäàòîâ çäåñü òðåáóåòñÿ âîçâðàùàòü ïî çàïðîñó x âñå îáú-
åêòû y áàçû, äëÿ êîòîðûõ | | ( ) ( ) | |g gx y� �� 1. Äëÿ ýòîãî ïðåäëàãàåòñÿ èñïîëüçîâàòü
3m ìîäèôèêàöèé õýøà çàïðîñà èëè 3m ìîäèôèêàöèé õýøà êàæäîãî îáúåêòà áàçû.
Ê ñîæàëåíèþ, êàíäèäàòàìè ìîãóò ÿâëÿòüñÿ îáúåêòû c áîëüøèì ðàññòîÿíèåì äî çà-
ïðîñà (äî cr, c D D s� max ,/ – /{ }1 2 1 1 ). Óñêîðåíèå çàïðîñà ðàññìîòðåíî â [49].
2.3.2. Ìîäåëè è âûáîð ïàðàìåòðîâ ÈÑ LSH äëÿ êîíêðåòíîé áàçû. Ó÷è-
òûâàÿ îñîáåííîñòè äàííûõ êîíêðåòíîé áàçû, ìîæíî óëó÷øèòü õàðàêòåðèñòèêè
ïîèñêà â ÈÑ LSH (ñì. òàêæå ïîäðàçä. 2.6.3). Â [24] âûáîð ïàðàìåòðîâ ïðîâîäÿò
ïåðåáîðîì èõ êîìáèíàöèé íà ïðîãðàììíîé ðåàëèçàöèè ðåàëüíîé LSH-ñòðóêòó-
ðû. Ýòî âû÷èñëèòåëüíî ñëîæíî, äàæå åñëè ðàáîòàòü ñ ïîäìíîæåñòâîì áàçû. Äëÿ
ðåøåíèÿ ýòîé ïðîáëåìû ïðåäëîæåíû [50, 45] ñòàòèñòè÷åñêèå ìîäåëè ÈÑ LSH
äëÿ L2LSH è âåðîÿòíîñòíîãî çàïðîñà (k)NN. Ìîäåëè èñïîëüçóþò ðàñïðåäåëåíèÿ
ðàññòîÿíèé ìåæäó çàïðîñîì è (k)NN, à òàêæå ìåæäó îáúåêòàìè áàçû.
 ìîäåëè ìóëüòèïðîáíîãî LSH [50] äëÿ ìàêñèìèçàöèè ïîëíîòû ïîèñêà âûáèðà-
åòñÿ ìàêñèìàëüíîå L, èñõîäÿ èç èìåþùåéñÿ ïàìÿòè. Ïðè çàäàííîì ñðåäíåì çíà÷åíèè
ïîëíîòû ïîèñêà íà áàçå îôëàéí íàñòðàèâàþòñÿ w â h U w( ) ( ,a r a� � � �� �) / è êîëè-
÷åñòâî êîíêàòåíèðóåìûõ ôóíêöèé m äëÿ ìèíèìèçàöèè âðåìåíè çàïðîñà (ñðåäíåé
äîëè îáúåêòîâ áàçû, êîòîðóþ ñîñòàâëÿþò êàíäèäàòû). Äëÿ êîíêðåòíîãî îáúåê-
òà-çàïðîñà íà îñíîâå ðàññòîÿíèé äî òåêóùèõ kNN íàñòðàèâàåòñÿ êîëè÷åñòâî ìîäè-
ôèêàöèé çàïðîñà äëÿ äîñòèæåíèÿ çàäàííîé ïîëíîòû ïîèñêà. Äåòàëüíàÿ ìî-
äåëü [45] ìèíèìèçèðóåò ñðåäíåå âðåìÿ ïîèñêà äëÿ çàäàííîé âåðîÿòíîñòè îøèáêè,
ìåíüøåé � (ñ óïðîùåííîé ìîäèôèêàöèåé çàïðîñà, áåç àäàïòàöèè ê çàïðîñó), è ìî-
æåò èñïîëüçîâàòüñÿ äëÿ íàñòðîéêè ïàðàìåòðîâ äëÿ ðàçëè÷íûõ òèïîâ çàïðîñîâ.
2.3.3. Àäàïòàöèÿ ê êîíêðåòíîìó çàïðîñó. Àäàïòàöèÿ ê êîíêðåòíîìó âåêòî-
ðó-çàïðîñó ðàññìàòðèâàëàñü â ìîäåëè ìóëüòèïðîáíîãî LSH [50]. Â [31] ïðåäëî-
æåíî óëó÷øàòü ñîîòíîøåíèå ñêîðîñòü–òî÷íîñòü ïîèñêà (â L2) âûáîðîì ïðè âû-
ïîëíåíèè çàïðîñà òåõ LSH-òàáëèö èç èõ èìåþùåãîñÿ íàáîðà, â êîòîðûõ âåê-
òîð-çàïðîñ ñ íàèáîëüøåé âåðîÿòíîñòüþ ïîïàäåò â îäíó êîðçèíó ñ áëèæàéøèì
ñîñåäîì. Èñïîëüçóåòñÿ êðèòåðèé ðåëåâàíòíîñòè õýø-êîðçèíû íà îñíîâå ðàññòîÿ-
íèÿ çàïðîñà äî öåíòðà êîðçèíû.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 175
 ðàáîòå [47] ðàññìàòðèâàþò çàïðîñ ( )� -rNN. Äëÿ áàçîâîé ÈÑ LSH è «òðóäíûõ»
çàïðîñîâ ñðåäíåå êîëè÷åñòâî êàíäèäàòîâ ìîæåò ñîñòàâëÿòü äî O nL( ), ãäå n — êîëè-
÷åñòâî îáúåêòîâ áàçû, ÿâëÿþùèõñÿ îòâåòàìè íà çàïðîñ. Äëÿ ðåøåíèÿ ýòîé ïðîáëåìû
â ìíîãîóðîâíåâîì àäàïòèâíîì LSH [47] ñòðîÿò íàáîðû (óðîâíè) LSH-òàáëèö äëÿ
ðàçëè÷íûõ ñî÷åòàíèé m è L ( L ðàñòåò ñ óâåëè÷åíèåì m). Ïðè âûïîëíåíèè çàïðîñà
â ýòîé ÈÑ ñðåäíåå êîëè÷åñòâî êàíäèäàòîâ � ( ( ) )n N n/ � âñåãäà ìåíüøå N , à âàðè-
àíò ÈÑ ñ ìîäèôèêàöèåé çàïðîñà ïðèáëèæàåò åãî ê íèæíåé ãðàíèöå O N n( )� � . Äëÿ
ðåàëèçàöèè ïîäõîäà íåîáõîäèìû áîëüøèå çàòðàòû ïàìÿòè.
 ïðàêòè÷åñêîì àëãîðèòìå [25] äëÿ çàïðîñà ( )� -rNN êîíñòðóèðóþò ÈÑ LSH
äëÿ ôèêñèðîâàííîãî L, âûáèðàÿ m pL� �� �log( ) / log/1 1
1� (ñì. ïîäðàçä. 2.1.2,
ñòðàòåãèÿ 2). ×òîáû ïðè âûïîëíåíèè êîíêðåòíîãî çàïðîñà âûáðàòü èñïîëüçîâà-
íèå áàçîâîé ÈÑ LSH ëèáî ëèíåéíîãî ïîèñêà, ïðåäëàãàåòñÿ áûñòðî îöåíèâàòü
âðåìÿ çàïðîñà äëÿ LSH. Äëÿ ýòîãî â HybridLSH [25] ñ êàæäîé õýø-êîðçèíîé àññî-
öèèðîâàíà ñòðóêòóðà Hyperloglog [51], êîòîðàÿ ïîçâîëÿåò àïïðîêñèìèðîâàòü ÷èñ-
ëî îáúåêòîâ áåç äóáëèêàòîâ â âûáðàííûõ õýøåì çàïðîñà L êîðçèíàõ.
2.3.4. Èñêëþ÷åíèå êàíäèäàòîâ ïî LSH-õýøàì. Îöåíêè âåðîÿòíîñòè ñîâïà-
äåíèÿ LSH-õýøåé îáúåêòîâ ìîãóò èñïîëüçîâàòüñÿ äëÿ áûñòðîé îáðàáîòêè êàíäèäà-
òîâ â öåëÿõ èñêëþ÷åíèÿ òåõ èç íèõ, äëÿ êîòîðûõ ìàëà âåðîÿòíîñòü ïðåâûøåíèÿ
ñõîäñòâîì ïîðîãîâîãî çíà÷åíèÿ [52]. Ïðèíèìàòü ðåøåíèå îá èñêëþ÷åíèè ìîæíî
ïîñëå îöåíêè ìàëîé ÷àñòè õýøåé èç èõ îáùåãî êîëè÷åñòâà. Íàïðèìåð, åñëè âñåãî
1000 õýøåé è èç ïåðâûõ 100 òîëüêî 10 ñîâïàäàþò, òî î÷åíü ìàëîâåðîÿòíî, ÷òî
ñõîäñòâî îáúåêòîâ ïðåâûøàåò 0.8. Áîëåå òîãî, ìîæíî îöåíèòü è ñàìó âåëè÷èíó
ñõîäñòâà ñ çàäàííîé ïîëüçîâàòåëåì òî÷íîñòüþ. Òðåáóþùèåñÿ äëÿ ýòîãî ôóíêöèè
ðàñïðåäåëåíèÿ âåðîÿòíîñòè âåëè÷èíû ñõîäñòâà ïðè óñëîâèè ñîâïàäåíèÿ çàäàííîé
äîëè õýø-çíà÷åíèé ïîëó÷åíû â [52] äëÿ LSH MinHash [27] (ñõîäñòâî Æàêêàðà)
è SimHash [22] (ñ ìîäèôèêàöèåé äëÿ êîñèíóñíîãî ñõîäñòâà). Ðàññìîòðåíî òàêæå
ïðèìåíåíèå äëÿ (íîðìèðîâàííûõ) ÿäåðíûõ ôóíêöèé ñõîäñòâà [52].
2.4. Ïîèñê ïðèáëèæåííûõ áëèæàéøèõ ñîñåäåé â èíäåêñíûõ ñòðóêòóðàõ
LSH. Òåîðåòè÷åñêè îáîñíîâàííàÿ áàçîâàÿ ÈÑ LSH äëÿ çàïðîñà ( , )c � -rNN1 òðåáó-
åò êîíñòðóèðîâàíèÿ íàáîðà òàáëèö ñî ñâîèìè ïàðàìåòðàìè äëÿ êàæäîé ñîâîêóï-
íîñòè r, c. Ïðè âûïîëíåíèè çàïðîñà âåðîÿòíîñòíîãî c-NN ïîñëåäîâàòåëüíîñòüþ
çàïðîñîâ ( , )c � -rNN1 ñ ðàçëè÷íûìè ðàäèóñàìè (ñì. ïîäðàçä. 1.2.3) ýòî ïðèâîäèò
ê áîëüøèì çàòðàòàì ïàìÿòè. Äëÿ ýêîíîìèè ïðåäëîæåíû àëãîðèòìû, ýìóëèðóþ-
ùèå çàïðîñû ñ ðàçëè÷íûìè ðàäèóñàìè â îäíîé ÈÑ íà îñíîâå LSH.
 LSH-forest [53] êîëè÷åñòâî m êîíêàòåíèðóåìûõ ôóíêöèé h ïåðåìåííîå —
òàêîå, ÷òîáû îáúåêòû áàçû ïîëó÷èëè ðàçëè÷íûå çíà÷åíèÿ LSH-õýøåé. Âìåñòî
õýø-òàáëèö èñïîëüçóþò ýêñïåðèìåíòàëüíî âûáèðàåìîå êîëè÷åñòâî L ïðåôèê-
ñíûõ äåðåâüåâ, â êîòîðûõ îáúåêòàì ñîîòâåòñòâóþò ëèñòîâûå óçëû. Óâåëè÷åíèå
ðàäèóñà çàïðîñà ýìóëèðóþò âûáîðîì îáúåêòîâ-êàíäèäàòîâ, õýøè êîòîðûõ èìåþò
÷àñòè÷íîå ñîâïàäåíèå ñ õýøåì çàïðîñà. Âíà÷àëå â êàæäîì äåðåâå íàõîäÿò ëèñò,
èìåþùèé íàèáîëüøèé ñîâïàäàþùèé ïðåôèêñ ñ çàïðîñîì. Çàòåì îñóùåñòâëÿþò
ñèíõðîííûé ïîóðîâíåâûé îáõîä L äåðåâüåâ ñ ñàìîãî íèæíåãî óðîâíÿ ê êîðíþ,
èçâëåêàÿ ëèñòüÿ-ïîòîìêè ðîäèòåëüñêèõ óçëîâ, ïîêà ÷èñëî êàíäèäàòîâ íå äîñòèã-
íåò çàäàííîãî. Èç êàíäèäàòîâ âûáèðàþò k áëèæàéøèõ ê çàïðîñó. Òåîðåòè÷åñêèé
àíàëèç [54] ðàññìàòðèâàåò ðàçíîâèäíîñòü LSH-forest êàê ïðàêòè÷åñêèé âàðèàíò
çàâèñÿùåãî îò äàííûõ LSH (ïîäðàçä. 2.6.3) äëÿ çàïðîñà ( , )c � -rNN1 (ñ ìåíüøèì
çíà÷åíèåì �, ÷åì äëÿ íå çàâèñÿùåãî îò äàííûõ LSH).
 LSB-tree [55] äëÿ ïîèñêà â L2 âíà÷àëå ñíèæàþò ðàçìåðíîñòü ñëó÷àéíûì
ïðîåöèðîâàíèåì ãàóññîâîé i.i.d. ìàòðèöåé. Âåêòîðû ïðåîáðàçóþò â çíà÷åíèÿ
Z-ïîðÿäêà [56], âåêòîðû áàçû èíäåêñèðóþò Â-tree [57]. Èñïîëüçóþò îäèíî÷íîå
äåðåâî èëè èõ ëåñ. Âûïîëíåíèå ñåðèè çàïðîñîâ ñ âîçðàñòàþùèì ðàäèóñîì ýìó-
ëèðóþò èçâëå÷åíèåì âåêòîðîâ èç ëèñòîâûõ óçëîâ â ïîðÿäêå óáûâàíèÿ êîëè÷åñòâà
ñîâïàäàþùèõ ñòàðøèõ áèòîâ Z-çíà÷åíèé.
 SKLSH [58] èñïîëüçóþò êëþ÷è, ÿâëÿþùèåñÿ êîíêàòåíàöèåé çíà÷åíèé õýøåé
L2LSH. Ïðåäëîæåíî ìåòðè÷åñêîå ðàññòîÿíèå ìåæäó êëþ÷àìè (íà îñíîâå ñîâïàäå-
176 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
íèÿ ïðåôèêñîâ è îòëè÷èÿ â ñëåäóþùåì êîìïîíåíòå), âåëè÷èíà êîòîðîãî îòðàæàåò
ðàññòîÿíèå L2 ìåæäó âåêòîðàìè. Ýòî ïîçâîëÿåò óïîðÿäî÷èòü êëþ÷è ïðè êîíñòðóè-
ðîâàíèè ÈÑ òàê, ÷òî êëþ÷è âåêòîðîâ áàçû, áëèçêèõ ê âåêòîðó çàïðîñà, õðàíÿòñÿ
â ïàìÿòè ðÿäîì. Èñïîëüçîâàíèå B+tree [57] ïîçâîëÿåò ïðè ïîèñêå èçâëåêàòü â ïåð-
âóþ î÷åðåäü îáúåêòû ñ êëþ÷àìè, áîëåå áëèçêèìè ê êëþ÷ó îáúåêòà-çàïðîñà. Ïðåè-
ìóùåñòâî íàä LSB-tree è C2LSH (ñì. äàëåå) äîñòèãàåòñÿ çà ñ÷åò èçâëå÷åíèÿ ãîðàçäî
áîëüøåãî ÷èñëà îáúåêòîâ-êàíäèäàòîâ ïðè çíà÷èòåëüíî ìåíüøåì ÷èñëå îïåðàöèé
ñëó÷àéíîãî ââîäà-âûâîäà.  [59] äëÿ óñêîðåíèÿ ïðèìåíÿþò ðàííèé îñòàíîâ SKLSH.
Ðàíæèðîâàòü êàíäèäàòîâ ïî êîëè÷åñòâó èõ âñòðå÷àåìîñòè â ñïèñêå êàíäèäà-
òîâ ïðåäëîæåíî â [60].  FBLSH [61] è C2LSH [62] â êà÷åñòâå êàíäèäàòîâ âûáè-
ðàþò îáúåêòû áàçû, äëÿ êîòîðûõ êîëè÷åñòâî ñîâïàäåíèé èíäèâèäóàëüíûõ
LSH-õýøåé h ñ LSH-õýøàìè çàïðîñà ïðåâûøàåò ïîðîãîâîå çíà÷åíèå.
Àíàëîãè÷íûé îòáîð èñïîëüçóåòñÿ â ðàáîòàõ [63, 64].
 C2LSH [62] èñïîëüçóþò óâåëè÷åíèå ðàäèóñîâ ïîèñêà { }1 2, , ,c c � ñ ïî-
ìîùüþ ìîäèôèêàöèè õýø-ôóíêöèé, â êà÷åñòâå êîòîðûõ ïðèìåíÿþò âàðèàíò
L2LSH. Ìîäèôèêàöèÿ îñóùåñòâëÿåòñÿ êàê � �h c( ) /� , ãäå h( )� — çíà÷åíèå
õýø-ôóíêöèè äëÿ ïðåäøåñòâóþùåãî ðàäèóñà.
 LazyLSH [63] âûïîëíÿþò çàïðîñû äëÿ ðàññòîÿíèé Ls, s�[ / , ]1 2 1 , ñ èñïîëüçî-
âàíèåì âàðèàíòà Ñ2LSH äëÿ L1LSH. Ðàäèóñ r äëÿ Ls, s�[ / , ]1 2 1 , àïïðîêñèìèðóþò
÷åðåç ðàäèóñ r äëÿ L1.  îòëè÷èå îò Ñ2LSH, ãäå óâåëè÷åíèå r ïðèâîäèò ê óâåëè÷å-
íèþ ðàçìåðà êîðçèí, êîòîðîå íå çàâèñèò îò îáúåêòà-çàïðîñà, â LazyLSH îáúåäèíÿþò
êîðçèíû, ñîñåäíèå ñ êîðçèíîé îáúåêòà-çàïðîñà, ÷òî ïîâûøàåò âåðîÿòíîñòü ñîâïàäå-
íèÿ õýøåé äëÿ áëèçêèõ ê çàïðîñó âåêòîðîâ áàçû. Ïðè îäíîâðåìåííîì âûïîëíåíèè
çàïðîñà äëÿ Ls ñ ðàçëè÷íûìè s óäàåòñÿ îïòèìèçèðîâàòü îáùåå âðåìÿ èçâëå÷åíèÿ
êàíäèäàòîâ. Ïîäõîä ìîæíî èñïîëüçîâàòü è ñ äðóãèìè ÈÑ äëÿ L1.
 QALSH [64] ïðè êîíñòðóèðîâàíèè ÈÑ äëÿ L2 íå èñïîëüçóþò ðàçáèåíèÿ
íà êîðçèíû, à èíäåêñèðóþò ñ ïîìîùüþ B+tree çíà÷åíèÿ ïðîåêöèè � �y r, âåêòîðîâ
áàçû y íà ñëó÷àéíûå íàïðàâëåíèÿ r. Ïðè ïîñòóïëåíèè çàïðîñà x îáúåêòû
áàçû â âèðòóàëüíîé êîðçèíå íàõîäÿò ïîèñêîì â B+tree â äèàïàçîíå
[ , / , , / ]� � � � � �x r x rwr wr2 2 . Áëàãîäàðÿ îòñóòñòâèþ ôèêñèðîâàííîãî ðàçáèåíèÿ íà
êîðçèíû, çàïðîñû ñ ðàäèóñàìè r èç { }1 2, , ,c c � ìîãóò âûïîëíÿòüñÿ ñ ëþáûì c �1.
 ýêñïåðèìåíòàõ QALSH ïðåâîñõîäèò C2LSH è LSB-forest.
 [65] èçâëåêàþò îáúåêòû-êàíäèäàòû â ïîðÿäêå óâåëè÷åíèÿ dist Ham èõ áèíàð-
íûõ LSH-õýøåé îò õýøåé îáúåêòà-çàïðîñà (äî äîñòèæåíèÿ êîëè÷åñòâà êàíäèäàòîâ,
ýìïèðè÷åñêè îïðåäåëÿåìîãî äëÿ çàäà÷è è äëÿ k). Äëÿ ïîèñêà ïî dist Ham èñïîëüçóþò
ñòðóêòóðó MIH [66] (âûïîëíÿÿ çàïðîñû ñ óâåëè÷èâàþùèìñÿ ðàäèóñîì). Áèíàðíûå
çíà÷åíèÿ õýøåé L2LSH ïîëó÷àþò âûáîðîì ïàðàìåòðà w â h U w( ) ( ,a r a� � � �� �) / .
Ýòîò BLSH âîçâðàùàåò áîëåå òî÷íûõ kNN çà ìåíüøåå âðåìÿ, ÷åì LSB, C2LSH,
SKLSH, îñîáåííî äëÿ äàííûõ áîëåå âûñîêîé ðàçìåðíîñòè (D �192).
 îòëè÷èå îò ðàññìîòðåííûõ ïîäõîäîâ â Selective Hashing [67] ïðåäëàãàåòñÿ
ñòðîèòü íàáîð ÈÑ LSH äëÿ êàæäîãî ðàäèóñà ïîèñêà èç { }r cr c r, , ,2
� , îäíàêî ïî-
ìåùàòü îáúåêò òîëüêî â êîðçèíó òàáëèöû äëÿ îäíîãî èç ðàäèóñîâ. Îáúåêòû áàçû
èç îáëàñòåé ïðîñòðàíñòâà ñ áîëüøîé ïëîòíîñòüþ ïîìåùàþò â êîðçèíû ñ ìåíü-
øèì ðàçìåðîì (ñîîòâåòñòâóþùèì ìåíüøåìó ðàäèóñó çàïðîñà). Ýòî ìîæíî ðàñ-
ñìàòðèâàòü êàê ïîäñòðîéêó ÈÑ ëîêàëüíî ê êàæäîìó îáúåêòó áàçû. Ïðè çàïðîñå
êàíäèäàòû èçâëåêàþò èç òàáëèö, íà÷èíàÿ ñ ìàëîãî ðàäèóñà, ïîêà â îñòàâøèõñÿ
ÈÑ åùå ìîãóò ñîäåðæàòüñÿ ïîòåíöèàëüíûå kNN. Òàê êàê óñëîâèå îñòàíîâà ó÷è-
òûâàåò ïîëîæåíèå îáúåêòà-çàïðîñà îòíîñèòåëüíî îáúåêòîâ áàçû, ïðîèñõîäèò
àäàïòàöèÿ ê çàïðîñó. Ýòîò ïðàêòè÷åñêèé ïîäõîä îáåñïå÷èâàåò çàòðàòû ïàìÿòè íà
óðîâíå áàçîâîé ÈÑ LSH äëÿ îäíîãî ðàäèóñà è ïîëíîòó ïîèñêà kNN íà óðîâíå ÈÑ
LSH äëÿ ìíîæåñòâà (óâåëè÷èâàþùèõñÿ) ðàäèóñîâ.
2.5. Ëîêàëüíî-÷óâñòâèòåëüíàÿ ôèëüòðàöèÿ è êîìïðîìèññ âðåìÿ/ïàìÿòü.
Áàçîâàÿ ÈÑ LSH ðàáîòàåò â ñèììåòðè÷íîì ðåæèìå: çíà÷åíèå � (ñì. ïîäðàçä. 2.1.2)
îäèíàêîâî êàê äëÿ âðåìåíè çàïðîñà, òàê è äëÿ çàòðàò ïàìÿòè (è âðåìåíè âñòàâêè/óäà-
ëåíèÿ îáúåêòîâ). Îäíàêî äëÿ íåêîòîðûõ ïðèìåíåíèé òðåáóåòñÿ àñèììåòðè÷íûé ðå-
æèì ñ ðàçëè÷íûìè êîìïðîìèññàìè ìåæäó óâåëè÷åíèåì çàòðàò ïàìÿòè è óìåíüøå-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 177
íèåì âðåìåíè âûïîëíåíèÿ çàïðîñà. Ïëàâíûé êîìïðîìèññ âðåìÿ/ïàìÿòü, îáåñïå÷è-
âàþùèé cóáëèíåéíîå âðåìÿ ïîèñêà â L2 äëÿ õóäøåãî ñëó÷àÿ äëÿ ëþáûõ c �1,
óëó÷øàþùèé ðåçóëüòàòû [46] äëÿ âñåõ c, ïîëó÷åí â [68] íà îñíîâå ïîäõîäà ëîêàëü-
íî-÷óâñòâèòåëüíîé ôèëüòðàöèè (locality-sensitive filtering, LSF) [69].
ÈÑ LSH àññîöèèðóþò êîðçèíó ñ êàæäûì çíà÷åíèåì LSH-ôóíêöèè, îáåñïå-
÷èâàÿ èñ÷åðïûâàþùåå ðàçáèåíèå ïðîñòðàíñòâà îáúåêòîâ: êàæäûé îáúåêò ïîïàäà-
åò â îäíó èç êîðçèí. LSF-ôèëüòð îòëè÷àåòñÿ òåì, ÷òî ïðîïóñêàåò òîëüêî ÷àñòü
âõîäíûõ îáúåêòîâ. Ñõîäíûå îáúåêòû èìåþò áîëüøóþ âåðîÿòíîñòü ïðåîäîëåòü
LSF-ôèëüòð, ÷åì íåñõîäíûå. LSF-ôèëüòðû ìîãóò èñïîëüçîâàòüñÿ èíäèâèäóàëüíî
èëè êîìáèíèðîâàòüñÿ ïîñëåäîâàòåëüíî è ïàðàëëåëüíî. Â [70] äëÿ áûñòðîé ýìóëÿ-
öèè áîëüøîãî êîëè÷åñòâà LSF-ôèëüòðîâ ïðåäëàãàåòñÿ ïîëó÷èòü îáúåêòû íà âû-
õîäå íåêîòîðîãî ìíîæåñòâà áàçîâûõ ôèëüòðîâ, à çàòåì ðåçóëüòàò íà âûõîäå îä-
íîãî ýìóëèðóåìîãî ôèëüòðà íàõîäèòü ïåðåñå÷åíèåì îáúåêòîâ ñîîòâåòñòâóþùåãî
åìó ïîäìíîæåñòâà áàçîâûõ.
 êîðçèíå çàïîìèíàþò îáúåêòû, êîòîðûå îñòàëèñü ïîñëå ïðîõîæäåíèÿ
LSF-ôèëüòðà èëè èõ ñîâîêóïíîñòè íà ïóòè ê íåé. Îäèí è òîò æå îáúåêò ìîæåò
ïðèíàäëåæàòü ðàçëè÷íûì êîðçèíàì. Ïðè âûïîëíåíèè çàïðîñà êàíäèäàòàìè ñòà-
íîâÿòñÿ îáúåêòû èç êîðçèí, â êîòîðûå ïðîøåë îáúåêò-çàïðîñ. Ïàðàìåòðû ôè-
ëüòðîâ ïðè êîíñòðóèðîâàíèè ÈÑ è ïðè âûïîëíåíèè çàïðîñà ìîãóò îòëè÷àòüñÿ,
÷òî è îáåñïå÷èâàåò óïîìÿíóòûé êîìïðîìèññ.
Ïðè ñîçäàíèè LSF-ôèëüòðîâ äëÿ ïîèñêà íà åäèíè÷íîé ñôåðå S D�1 â [69]
è [68] èñïîëüçóþò èäåþ ðàçáèåíèÿ ñôåðû íà îáëàñòè áîëüøèì êîëè÷åñòâîì ìà-
ëûõ ñôåðè÷åñêèõ ñåãìåíòîâ (spherical cap, SC). Âåêòîð a ïðèíàäëåæèò ê SC ( , )r t ,
åñëè � � �r a, t , r — ñëó÷àéíûé ãàóññîâ âåêòîð èëè ñëó÷àéíûé âåêòîð ñ S D�1.
(Îòìåòèì, ÷òî àíàëîãè÷íîå ïðåîáðàçîâàíèå ïðèìåíÿåòñÿ äëÿ ïîëó÷åíèÿ ðàçðå-
æåííûõ áèíàðíûõ/òåðíàðíûõ âåêòîðîâ â [71–74].) Ïîðîã tu , èñïîëüçóåìûé ïðè
ïîñòðîåíèè ÈÑ, ìîæåò îòëè÷àòüñÿ îò tq ïðè îáðàáîòêå çàïðîñà.
Ïðè áîëüøîì êîëè÷åñòâå SC îïðåäåëèòü, ê êàêèì èç íèõ ïðèíàäëåæèò âåê-
òîð, âû÷èñëèòåëüíî òðóäîåìêî. Äëÿ ðåøåíèÿ ýòîé ïðîáëåìû â [68] êàæäîé îá-
ëàñòè-êîðçèíå ñîîòâåòñòâóåò ïåðåñå÷åíèå íåñêîëüêèõ SC. Äëÿ îïðåäåëåíèÿ, ê êà-
êîé êîðçèíå ïðèíàäëåæèò îáúåêò, èñïîëüçóþò äåðåâî ñ A �1 óðîâíÿìè, ãäå êàæ-
äûé óçåë ñîîòâåòñòâóåò SC. Êîýôôèöèåíò âåòâëåíèÿ íå ïðåâûøàåò M , ïîýòîìó
íà óðîâíå A íå áîëåå M A ëèñòüåâ. Óçëû õðàíÿò ïî îäíîìó i.i.d. ñëó÷àéíîìó âåê-
òîðó èç Norm ( , )0 I . Ïðè ïîñòðîåíèè ÈÑ ìíîæåñòâî âåêòîðîâ-îáúåêòîâ íåêîòîðî-
ãî óçëà ðàçáèâàåòñÿ åãî ñûíîâüÿìè íà M (âîçìîæíî ïåðåñåêàþùèõñÿ) ïîäìíî-
æåñòâ, êàæäîå îïðåäåëÿåòñÿ ïî � � �r y, tu . Äëÿ óçëîâ ñ íåïóñòûì ìíîæåñòâîì
îáúåêòîâ ðàçáèåíèå ïîâòîðÿþò, ïîêà íå äîñòèãàþò A-ãî óðîâíÿ äåðåâà.
Ïðè îáðàáîòêå âåêòîðà-çàïðîñà ñòàðòóþò ñ êîðíÿ è ïåðåõîäÿò íà ñûíîâåé,
äëÿ êîòîðûõ � � �r x, tq . Êàíäèäàòàìè ÿâëÿþòñÿ âåêòîðû èç óçëîâ A-ãî óðîâíÿ, äî
êîòîðûõ äîøåë âåêòîð-çàïðîñ. Âûáîð ïàðàìåòðîâ A, M , tu è tq çàâèñèò îò r, c,
à òàêæå � u è � q . Åñëè t tu q� òî � u= � q è ïîëó÷àþò ðåæèì LSH. Ýòà ÈÑ
ïðàêòè÷åñêè íå ðåàëèçîâàíà.
 [69] ïðåäëîæåí ðåàëèçîâàííûé àëãîðèòì. Ëèñòó ñîîòâåòñòâóåò ñôåðè÷åñêèé
ñåãìåíò, îäíàêî âåêòîð, åãî îïðåäåëÿþùèé, ñîñòîèò èç A D� �(log ) âåêòîðîâ-÷àñ-
òåé ðàçìåðíîñòè D A/ . Äëÿ êàæäîé ÷àñòè ñëó÷àéíî ãåíåðèðóþò M âåêòîðîâ ñ S D�1
è íîðìèðóþò èõ, ÷òîáû îáåñïå÷èòü åäèíè÷íóþ íîðìó ïîëíîãî âåêòîðà. Èç âåêòî-
ðîâ-÷àñòåé ìîæíî ñîñòàâèòü M A ðàçëè÷íûõ âåêòîðîâ r ðàçìåðíîñòè D, ñîîòâå-
òñòâóþùèõ êîðçèíàì. Ïîêàçàíî, ÷òî âåðîÿòíîñòü ïîïàäàíèÿ âåêòîðîâ â êîðçèíó
ñ ñîñòàâíûì r áëèçêà ê âåðîÿòíîñòè äëÿ ñëó÷àéíûõ r ñ S D�1.
Äëÿ áûñòðîãî îïðåäåëåíèÿ, ê êàêîé êîðçèíå ïðèíàäëåæèò âõîäíîé âåêòîð,
ñòðîÿò ÈÑ â âèäå A-óðîâíåâîãî äåðåâà ñ êîýôôèöèåíòîì âåòâëåíèÿ M , ãäå êàæ-
äîìó óçëó ñîîòâåòñòâóåò ñëó÷àéíûé âåêòîð-÷àñòü. Äëÿ êàæäîé èç A ÷àñòåé âõîä-
íîãî âåêòîðà âû÷èñëÿþò M ñêàëÿðíûõ ïðîèçâåäåíèé ñ âåêòîðàìè óçëîâ, ÷òî ïî-
çâîëÿåò áûñòðî îïðåäåëèòü (ñîîòâåòñòâóþùèå ëèñòüÿì) êîðçèíû, ê êîòîðûì ïðè-
íàäëåæèò âõîäíîé âåêòîð (ñëîæíîñòü âû÷èñëåíèé â A ðàç ïðåâûøàåò êîëè÷åñòâî
êîðçèí, ê êîòîðûì ïðèíàäëåæèò âåêòîð). Çíà÷åíèÿ tu è tq ìîãóò îòëè÷àòüñÿ.
178 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
 ñèììåòðè÷íîì ðåæèìå � �u q� òàêàÿ ÈÑ ïîçâîëÿåò ïîëó÷èòü ìåíü-
øèå çíà÷åíèÿ �, ÷åì ñôåðè÷åñêèé è ãèïåðîêòàýäðíûé LSH (ñì. ïîäðàçä. 2.2.1)
äëÿ äàííûõ ñ D O N� (log ) . Äëÿ õóäøåãî ñëó÷àÿ ýòè íåçàâèñèìûå îò äàííûõ ÈÑ
ïîçâîëÿþò äîñòè÷ü ãèáêîãî êîìïðîìèññà âðåìÿ/ïàìÿòü ( )c q
2 1� ��
� � �( )c cu
2 1 2� . Ðàñøèðåíèå ñ S D�1 íà âñå L2 (ïîäðàçä. 2.6.1) ïîçâîëÿåò äëÿ
âñåõ ñâÿçàííûõ ýòèì âûðàæåíèåì c �1, r � 0 è � u , � q ïîëó÷èòü ÈÑ äëÿ çàïðîñà
( , )c � -rNN1 â L2 ñ çàòðàòàìè ïàìÿòè N u o1 1� �� ( )
è âðåìåíåì çàïðîñà
N DNq o o� �
�
( ) ( )1 1 . Äëÿ � u= � q ïîëó÷àþò � � 1 2/ c . Ðàñøèðåíèå íà äðóãèå Ls
ðàññìîòðåíî â ïîäðàçä 2.6.1. Çàâèñèìûå îò äàííûõ ÈÑ ïîçâîëÿþò óëó÷øèòü õà-
ðàêòåðèñòèêè (ïîäðàçä. 2.6.3).
2.6. Íåêîòîðûå òåîðåòè÷åñêèå àñïåêòû è àäàïòàöèÿ ê äàííûì
2.6.1. Ðàñøèðåíèÿ íà Ls . Ðåçóëüòàòû àíàëèçà ÈÑ äëÿ ïîèñêà â S D�1 ðàñïðîñ-
òðàíÿþò íà âñå åâêëèäîâî ïðîñòðàíñòâî, èñïîëüçóÿ ðåäóêöèþ L2 ê S D�1 [75], ñî-
õðàíÿþùóþ îòíîøåíèå ðàññòîÿíèé L2 (ñ ìóëüòèïëèêàòèâíûì èñêàæåíèåì).
×òîáû ðàñøèðèòü ðåçóëüòàòû äëÿ L2 íà Ls, èñïîëüçóþò äåòåðìèíèðîâàííîå
ïîêîìïîíåíòíîå âëîæåíèå [76] (ñ ìóëüòèïëèêàòèâíûì è àääèòèâíûì èñêàæåíè-
åì) èç Ls ( 1 2�
s ) â L s
2
2/ (ñ ñîîòâåòñòâóþùèì èçìåíåíèåì r). Ðàñøèðåíèÿ íà Ls
áàçîâîé ÈÑ LSH â L2 , äëÿ êîòîðîé � � �1 12/ ( )c o (ñì. [30] è ïîäðàçä. 2.2), äàþò
äëÿ Ls çíà÷åíèå � � �1 1/ ( )c os [12].
×òîáû ðàñøèðèòü ðåçóëüòàòû àíàëèçà ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ïî ñêà-
ëÿðíîìó ïðîèçâåäåíèþ âåêòîðîâ ñ S D�1 (÷òî ýêâèâàëåíòíî ïîèñêó ïî åâêëèäîâó
ðàññòîÿíèþ, ñì. ïîäðàçä. 1.1) íà Ls (0 2
�s ), â [70] ïðåäëàãàåòñÿ èñïîëüçîâàòü
ïðèáëèæåííîå âëîæåíèå ÿäåðíîãî ñõîäñòâà D-ìåðíûõ âåêòîðîâ
�( ) exp( | | | | )a b a b� � � � s
s , 0 2
�s , â ñêàëÿðíîå ïðîèçâåäåíèå âåêòîðîâ íà S D�1
([77] è îáçîðû [1, 2]). Òîãäà âûïîëíåíèå çàïðîñà ( , )c � -rNN1 â Ls ýêâèâàëåíòíî
âûïîëíåíèþ àíàëîãè÷íîãî çàïðîñà ïî sim dot âåêòîðîâ ñ S D�1 ñî çíà÷åíèåì
ñõîäñòâà exp( )�r s (ñ ïîïðàâêîé íà èñêàæåíèå âëîæåíèÿ).
Îòìåòèì, ÷òî â ïðàêòè÷åñêèõ ÈÑ ðåäóêöèè ýòîãî ïîäðàçäåëà íå âñòðå÷àþòñÿ.
2.6.2. Ãðàíèöû. Àíàëèç ïðåäëîæåííûõ àëãîðèòìîâ ïîèñêà ïî ñõîäñòâó (íå
âñåãäà ïðàêòè÷åñêè ðåàëèçóåìûõ) ïîçâîëÿåò ïîëó÷èòü âåðõíèå ãðàíèöû çàòðàò
ïàìÿòè è âðåìåíè çàïðîñà. Íèæíèå ãðàíèöû äëÿ âåùåñòâåííûõ âåêòîðîâ ñ ðàñ-
ñòîÿíèåì Ls îáû÷íî ïîëó÷àþò ÷åðåç äîêàçàííûå (äëÿ íåêîòîðûõ «òðóäíûõ» ðàñ-
ïðåäåëåíèé äàííûõ) íèæíèå ãðàíèöû äëÿ ïîèñêà áèíàðíûõ âåêòîðîâ { }0 1, D ïî
dist Ham , èñïîëüçóÿ dist Ham ( , ) | | | |a b a b� � s
s. Ïðèìåíåíèå Ls
s âìåñòî dist Ham
òðàíñôîðìèðóåò c â cs â âûðàæåíèè äëÿ � [12]. Äëÿ áîëåå îáùåãî ñëó÷àÿ âåùåñò-
âåííûõ âåêòîðîâ íèæíÿÿ ãðàíèöà íå ìîæåò áûòü ìåíüøåé, ÷åì äëÿ áèíàðíûõ.
Äëÿ áàçîâîãî LSH èç íèæíåé ãðàíèöû äëÿ ðàññòîÿíèÿ Õýììèíãà
� � �1 1/ ( )c oD [78] ñëåäóåò � � �1 1/ ( )c os
D äëÿ Ls. Äëÿ øèðîêîãî êëàññà íåçàâè-
ñèìûõ îò äàííûõ ÈÑ list-of-points (êîòîðûé âêëþ÷àåò è LSH, è LSF) äëÿ áèíàð-
íûõ âåêòîðîâ ñ D N� �(log ) ïîêàçàíà [68] íèæíÿÿ ãðàíèöà äëÿ âñåãî äèàïàçîíà
� u , � q : c c cq u� �� � � �( )1 2 1 ñ çàìåíîé c íà cs äëÿ1 2� �s . Ýòà íèæíÿÿ ãðà-
íèöà � ñ òî÷íîñòüþ äî ñëàãàåìûõ o( )1 ñîîòâåòñòâóåò âåðõíåé ãðàíèöå äëÿ ðàçáèå-
íèé, çàâèñèìûõ îò äàííûõ (ïîäðàçä. 2.6.3). Äëÿ � u= � q è L1 ïîëó÷àåì � � �1 2 1/ ( )c ,
à äëÿ L2 èìååì � � �1 2 12/ ( )c , ÷òî ñîîòâåòñòâóåò íèæíèì ãðàíèöàì è äëÿ çàâèñèìîãî îò
äàííûõ LSH. Àíàëèç íèæíåé ãðàíèöû äëÿ s� 2 â íàñòîÿùåå âðåìÿ íå ïðîâåäåí.
2.6.3. Àäàïòàöèÿ ê äàííûì. Èíäåêñíûå ñòðóêòóðû, êîòîðûå àäàïòèðóþòñÿ
ê äàííûì áàçû, íà ïðàêòèêå çà÷àñòóþ ïðåâîñõîäÿò ÈÑ, êîíñòðóèðóåìûå íåçàâè-
ñèìî îò äàííûõ, õîòÿ â áîëüøèíñòâå è íå äàþò ãàðàíòèé õóäøåãî ñëó÷àÿ. Ýòî
ñïðàâåäëèâî òàêæå äëÿ ïîèñêà ïî ñõîäñòâó ïî ïðåäñòàâëåíèÿì, ñôîðìèðîâàííûì
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 179
îáó÷åíèåì. Îáçîðû ÈÑ è ôîðìèðîâàíèÿ ïðåäñòàâëåíèé ñ îáó÷åíèåì ïðåäñòàâëå-
íû â [26, 79–81].
 [82] ïðèâåäåí òåîðåòè÷åñêèé àíàëèç óìåíüøåíèÿ âðåìåíè çàïðîñà ïî ñðàâ-
íåíèþ ñ õóäøèì ñëó÷àåì è âûáîð ïàðàìåòðîâ äëÿ íåçàâèñèìîãî îò äàííûõ LSH,
êîòîðûé ðàáîòàåò ñ õîðîøî ðàññðåäîòî÷åííûìè äàííûìè èëè ñ äàííûìè íèçêîé
âíóòðåííåé ðàçìåðíîñòè.
Àäàïòàöèÿ ÈÑ ê äàííûì áàçû, ïîçâîëÿþùàÿ óëó÷øèòü õàðàêòåðèñòèêè ÈÑ
äëÿ äàííûõ õóäøåãî ñëó÷àÿ, ðàññìîòðåíà â [83, 39, 68, 54]. Îêàçûâàåòñÿ, äëÿ íå-
êîòîðûõ («ïñåâäîñëó÷àéíûõ») êîíôèãóðàöèé (ðàñïîëîæåíèé) îáúåêòîâ áàçû
ìîæíî ñêîíñòðóèðîâàòü íåçàâèñèìûå îò äàííûõ ÈÑ ñ ìåíüøèì �, ÷åì äëÿ äàí-
íûõ õóäøåãî ñëó÷àÿ. Îáúåêòû áàçû õóäøåãî ñëó÷àÿ ðàçáèâàþò íà ïîäìíîæåñòâà,
êîòîðûå ñâîäÿò ê òàêèì êîíôèãóðàöèÿì.
 [83] óëó÷øåíèå � äëÿ LSH äëÿ L2 ïîëó÷åíî ïðè äîñòàòî÷íî áîëüøèõ c,
à â [39] ðåçóëüòàòû óëó÷øåíû äî òåîðåòè÷åñêè îïòèìàëüíûõ [84]
� � � �1 2 1 12/ ( ) ( )c o äëÿ âñåõ c.  [68] ïîëó÷åí (îïòèìàëüíûé äëÿ øèðîêîãî êëàñ-
ñà ÈÑ) êîìïðîìèññ ìåæäó � u , � q : c c cq u
2 2 21 2 1� �� � � �( ) . Ê ñîæàëå-
íèþ, âñëåäñòâèå ñëîæíîñòè ðåäóêöèè äàííûõ õóäøåãî ñëó÷àÿ ê «ïñåâäîñëó÷àé-
íûì» êîíôèãóðàöèÿì ìåòîäû [83, 39, 68] ïðàêòè÷åñêè íå ðåàëèçîâàíû.  [54]
ïðèâåäåí àíàëèç ïðàêòè÷åñêîé ñõåìû (ìîäèôèêàöèè LSH-forest), â êîòîðîé õà-
ðàêòåðèñòèêè äëÿ äàííûõ õóäøåãî ñëó÷àÿ ïðåâîñõîäÿò íåçàâèñèìûé îò äàííûõ
LSH (õîòÿ è óñòóïàþò îïòèìàëüíûì ãðàíèöàì [39]).
ÇÀÊËÞ×ÅÍÈÅ
Ïðåèìóùåñòâî ðàññìîòðåííûõ â äàííîé ñòàòüå ÈÑ íà îñíîâå ëîêàëüíî-÷óâñòâè-
òåëüíîãî õýøèðîâàíèÿ è èõ ìîäèôèêàöèé çàêëþ÷àåòñÿ â òåîðåòè÷åñêè îáîñíîâàí-
íîì âûáîðå ïàðàìåòðîâ ÈÑ, ïîçâîëÿþùåì ãàðàíòèðîâàòü ñóáëèíåéíîå îòíîñè-
òåëüíî êîëè÷åñòâà îáúåêòîâ â áàçå âðåìÿ âûïîëíåíèÿ íåêîòîðûõ òèïîâ çàïðîñîâ
ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó äëÿ õóäøåãî ñëó÷àÿ. Âî âòîðîé ÷àñòè îáçîðà
áóäåò ïðåäñòàâëåíî îáñóæäåíèå è ñðàâíåíèå ýòîãî ïîäõîäà ñ ÈÑ íà îñíîâå: ÿâ-
íîãî èñïîëüçîâàíèÿ îáëàñòåé (äðåâîâèäíûå è äð.), ãðàôîâ ñîñåäñòâà [3], ïðåîáðà-
çîâàíèÿ èñõîäíûõ (âåùåñòâåííûõ âåêòîðíûõ) ïðåäñòàâëåíèé îáúåêòîâ, àâòîàññî-
öèàòèâíîé ïàìÿòè [85]. Îòìåòèì, ÷òî ñïåöèàëèçèðîâàííûé äëÿ ñõîäñòâà Æàêêàðà
ìåæäó áèíàðíûìè ðàçðåæåííûìè âåêòîðàìè î÷åíü áîëüøîé ðàçìåðíîñòè õîðîøî
ïàðàëëåëèçóåìûé àëãîðèòì FLASH [86] (ìîäèôèöèðîâàííûé âàðèàíò ÈÑ LSH,
èñïîëüçóþùèé MinHash c îäíîé ïåðåñòàíîâêîé äëÿ ïîëó÷åíèÿ áîëüøîãî êîëè-
÷åñòâà õýø-çíà÷åíèé [87], êîðçèíû îãðàíè÷åííîãî ðàçìåðà çà ñ÷åò ñýìïëèðîâà-
íèÿ, îáùèå êîðçèíû äëÿ ðàçëè÷íûõ LSH-òàáëèö, ðàíæèðîâàíèå îáúåêòîâ-êàíäè-
äàòîâ ïî ÷àñòîòå èõ âñòðå÷àåìîñòè áåç âû÷èñëåíèÿ èñõîäíûõ ðàññòîÿíèé/ñõîäñòâ
äî îáúåêòà-çàïðîñà) ïðîäåìîíñòðèðîâàë ïðåèìóùåñòâî íàä âñåìè äðóãèìè ÈÑ.
Àâòîð áëàãîäàðåí Alex Andoni çà ðàçúÿñíåíèÿ íåêîòîðûõ àñïåêòîâ åãî èñ-
ñëåäîâàíèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Rachkovskij D.A. Real-valued embeddings and sketches for fast distance and similarity estimation.
Cybernetics and Systems Analysis. 2016. Vol. 52, N. 6. P. 967–988.
2. Rachkovskij D.A. Binary vectors for fast distance and similarity estimation. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 1. P. 138–156.
3. Rachkovskij D.A. Distance-based index structures for fast similarity search. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 4. P. 636–658.
4. Rachkovskij D.A. Index structures for fast similarity search for binary vectors. Cybernetics and
Systems Analysis. 2017. Vol. 53, N 5. P. 799–820.
5. Manning C., Raghavan P., Sch��utze H. Introduction to information retrieval. New York: Cambridge
University Press, 2008. 506 p.
6. Datta R., Joshi D., Li J., Wang J. Image retrieval: Ideas, influences, and trends of the new age. ACM
Computing Surveys. 2008. Vol. 40, N 2. P. 1–60.
7. Fouad Ì.Ì. Content-based search for image retrieval. Int. J. Image, Graphics and Signal
Processing. 2013. Vol. 5, N 11. P. 46–52.
180 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
8. Khalifa F.A., Semary N.A., El-Sayed H.M., Hadhoud M.M. Local detectors and descriptors for object
class recognition. Int. J. of Intelligent Systems and Applications. 2015. Vol. 7, N 10. P. 12–18.
9. Ziomek A., Oszust M. Evaluation of interest point detectors in presence of noise. Int. J. Intelligent
Systems and Applications. 2016. Vol. 8, N 3. P. 26–33.
10. Fortune S. Voronoi diagrams and Delaunay triangulations. Chap. 27. Handbook of Discrete and
Computational Geometry, 3rd edition. Boca Raton, USA: CRC Press. 2017. P. 705–721.
11. Meiser S. Point location in arrangements of hyperplanes. Inform. and Comput. 1993. Vol. 106, N 2.
P. 286–303.
12. Andoni A., Indyk P. Nearest neighbors in high-dimensional spaces.Chap. 43. Handbook of Discrete and
Computational Geometry, 3rd edition. Boca Raton, USA: CRC Press. 2017. P. 1133–1153.
13. Weber R., Schek H., Blott S. A quantitative analysis and performance study for similarity-search
methods in high-dimensional spaces. Proc. VLDB’98. 1998. P. 194–205.
14. Arya S., Mount D., Netanyahu N., Silverman R., Wu A. An optimal algorithm for approximate
nearest neighbor searching fixed dimensions. Journal of the ACM. 1998. Vol. 45, N 6. P. 891–923.
15. Andoni A., Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high
dimensions. Communications of the ACM. 2008. Vol. 51. N 1. P. 117–122.
16. Har-Peled S., Indyk P., Motwani R. Approximate nearest neighbor: Towards removing the curse of
dimensionality. Theory Comput. 2012. Vol. 8. P. 321–350.
17. Powers D.M.W. Evaluation: from precision, recall and F-measure to ROC, informedness,
markedness and correlation. J. of Machine Learning Tech. 2011. Vol. 2, N 1. P. 37–63.
18. Das R., Thepade S., Ghosh S. Content based image recognition by information fusion with multiview
features. I. J. Information Technology and Computer Science. 2015. Vol. 7, N 10. P. 61–73.
19. Ramaswamy S., Rose K. Adaptive cluster distance bounding for high-dimensional indexing. IEEE
Trans. on KDE. 2011. Vol. 23, N 6. P. 815–830.
20. Muja M., Lowe D.G. Scalable nearest neighbor algorithms for high dimensional data. IEEE TPAMI.
2014. Vol. 36, N 11. P. 2227–2240.
21. Shrivastava A., Li P. Asymmetric minwise hashing for indexing binary inner products and set
containment. Proc. WWW’15. 2015. P. 981–991.
22. Charikar M. Similarity estimation techniques from rounding algorithms. Proc. STOC’02. 2002.
P. 380–388.
23. Aumuller M., Christiani T., Pagh R., Silvestr F. Distance sensitive hashing. arXiv:1703.07867.
22 Mar 2017.
24. Andoni A., Datar M., Immorlica N., Indyk P., Mirrokni V.S. Locality-sensitive hashing using stable
distributions. Nearest Neighbor Methods for Learning and Vision: Theory and Practice. Cambridge:
MIT Press, 2006. P. 61–72.
25. Pham N. Hybrid LSH: Faster near neighbors reporting in high-dimensional space. Proc. EDBT’17.
2017. P. 454–457.
26. Wang J., Shen H.T., Song J., Ji J. Hashing for similarity search: A survey. arXiv:1408.2927.
13 Aug 2014.
27. Tang J., Tian Y. A systematic review on minwise hashing algorithms. Annals of Data Science. 2016.
Vol. 3, N 4. P. 445–468.
28. Kulis B., Grauman K. Kernelized locality-sensitive hashing. IEEE Trans. PAMI. 2012. Vol. 34, N 6.
P. 1092–1104.
29. Mu Y., Yan S. Non-metric locality sensitive hashing. Proc. AAAI’10. 2010. P. 539–544.
30. Andoni A., Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high
dimensions. Proc. FOCS’06. 2006. P. 459-468.
31. Jegou H., Amsaleg L., Schmid C., Gros P. Query-adaptive locality sensitive hashing. Proc.
ICASSP’08. 2008. P. 825–828.
32. Chierichetti F., Kumar R. Lsh-preserving functions and their applications. J. ACM. 2015. Vol. 62,
N 5. P. 33:1–33:25.
33. Chierichetti F., Kumar R., Panconesi A., Terolli E. The distortion of locality sensitive hashing. Proc.
ITCS’17. 2017. 23 p.
34. Sokolov A. Investigation of accelerated search for close text sequences with the help of vector
representations. Cybernetics and Systems Analysis. 2008. Vol. 44, N 4. P. 493–506.
35. Andoni A., Krauthgamer R., Razenshteyn I.P. Sketching and embedding are equivalent for norms.
Proc. STOC’15. 2015. P. 479–488.
36. Andoni A., Indyk P., Laarhoven T., Razenshteyn I., Schmidt L. Practical and optimal LSH for
angular distance. Proc. NIPS’15. 2015. P. 1225-1233.
37. Terasawa K., Tanaka Y. Spherical lsh for approximate nearest neighbor search on unit hypersphere.
Proc. WADS’07. 2007. P. 27–38.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 181
38. Eshghi K., Rajaram S. Locality sensitive hash functions based on concomitant rank order statistics.
Proc. KDD’08. 2008. P. 221–229.
39. Andoni A., Razenshteyn I. Optimal data-dependent hashing for approximate near neighbors. Proc.
STOC’15. 2015. P. 793–801.
40. Laarhoven T. Hypercube LSH for approximate near neighbors. Proc. MFCS’17. 2017.
41. Kennedy C., Ward R. Fast cross-polytope locality-sensitive hashing. Proc. ITCS’17. 2017.
42. Panigrahy R. Entropy based nearest neighbor search in high dimensions. Proc. SODA’06. 2006.
P. 1186–1195.
43. Lv Q., Josephson W., Wang Z., Charikar M., Li K. Multi-probe lsh: efficient indexing for
high-dimensional similarity search. Proc. VLDB’07. 2007. P. 950–961.
44. Joly A., Buisson O. A posteriori multi-probe locality sensitive hashing. Proc. MM’08. 2008.
P. 209–218.
45. Slaney M., Lifshits Y., He J. Optimal parameters for locality-sensitive hashing. Proc. of the IEEE.
2012. Vol. 100, N 9. P. 2604–2623.
46. Kapralov M. Smooth tradeoffs between insert and query complexity in nearest neighbor search.
Proc. PODS’15. 2015. P. 329–342.
47. Ahle T.D., Aumuller M., Pagh R. Parameter-free locality sensitive hashing for spherical range
reporting. Proc. SODA’17. 2017. P. 239–256.
48. Pacuk A., Sankowski P., Wegrzycki K., Wygocki P. Locality-sensitive hashing without false
negatives for lp. Proc. COCOON’16. 2016. P. 105–118.
49. Wygocki P. On fast bounded locality sensitive hashing. arXiv:1704.05902. 19 Apr 2017.
50. Dong W., Wang Z., Josephson W., Charikar M., Li K. Modeling lsh for performance tuning. Proc.
CIKM’08. 2008. P. 669–678.
51. Flajolet P., Fusy E., Gandouet O., Meunier F. Hyperloglog: The analysis of a near-optimal
cardinality estimation algorithm. Proc. AofA’07. 2007. P. 127–146.
52. Chakrabarti A., Satuluri V., Srivathsan A., Parthasarathy S. A Bayesian perspective on locality
sensitive hashing with extensions for kernel methods. ACM TKDD. 2015. Vol. 10, N 2. P. 19:1–19:32.
53. Bawa M., Condie T., Ganesan P. Lsh forest: self-tuning indexes for similarity search. Proc.
WWW’05. 2005. P. 651–660.
54. Andoni A., Razenshteyn I., Shekel Nosatzki N. Lsh forest: Practical algorithms made theoretical.
Proc. SODA’17. 2017. P. 67–78.
55. Tao Y., Yi K., Sheng C., Kalnis P. Efficient and accurate nearest neighbor and closest pair search in
high dimensional space. ACM TODS. 2010. Vol. 35, N 3. P. 20:1–20:46.
56. Lawder J.K., King P.J.H. Querying multi-dimensional data indexed using the hilbert space filling
curve. ACM SIGMOD Record. 2001. Vol. 30, N 1. P. 19–24.
57. Comer D. The ubiquitous B-tree. ACM Comput. Surv. 1979. Vol. 11. P. 121–138.
58. Liu Y., Cui J., Huang Z., Li H., Shen H.T. Sk-lsh: An efficient index structure for approximate
nearest neighbor search. Proc. VLDB Endowment. 2014. Vol. 7, N 9. P. 745-756.
59. Chen J., He C., Hu G., Shao J. SELSH: a hashing scheme for approximate similarity search with
early stop condition. Proc. MMM’16. 2016. Vol. 2. P. 104–115.
60. Hao F., Daugman J., Zielinski P. A fast search algorithm for a large fuzzy database. IEEE Trans.
Information Forensics and Security. 2008. Vol. 3, N 2. P. 203–212.
61. Ling K., Wu G. Frequency based locality sensitive hashing. Proc. ICMT’11. 2011. P. 4929–4932.
62. Gan J., Feng J., Fang Q., Ng W. Locality-sensitive hashing scheme based on dynamic collision
counting. Proc. SIGMOD’12. 2012. P. 541–552.
63. Zheng Y., Guo Q., Tung A.K.H., Wu S. LazyLSH: Approximate nearest neighbor search for
multiple distance functions with a single index. Proc. SIGMOD’16. 2016. P. 2023–2037.
64. Huang Q., Feng J., Zhang Y., Fang Q., Ng W. Query-aware locality-sensitive hashing for
approximate nearest neighbor search. Proc. VLDB Endowment. 2015. Vol 9, N 1. P. 1–12.
65. Zhang X., Wang M., Cui J. Efficient indexing of binary LSH for high dimensional nearest neighbor.
Neurocomputing. 2016. Vol. 213. P. 24–33.
66. Norouzi M., Punjani A., Fleet D.J. Fast exact search in Hamming space with multi-index hashing.
IEEE Trans. PAMI. 2014. Vol. 36, N 6. P. 1107–1119.
67. Gao J., Jagadish, H.V., Ooi B.C., Wang S. Selective hashing: Closing the gap between radius search
and k-NN search. Proc. SIGKDD’15. 2015. P. 349–358.
68. Andoni A., Laarhoven T., Razenshteyn I., Waingarten E. Optimal hashing-based time-space
trade-offs for approximate near neighbors. Proc. SODA’17. 2017. P. 47–66.
69. Becker A., Ducas L., Gama N., Laarhoven T. New directions in nearest neighbor searching with
applications to lattice sieving. Proc. SODA’16. 2016. P. 10–24.
70. Christiani T. A framework for similarity search with space-time tradeoffs using locality-sensitive
filtering. Proc. SODA’17. 2017. P. 31–46.
182 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1
71. Rachkovskij D.A., Misuno I.S., Slipchenko S.V. Randomized projective methods for construction of
binary sparse vector representations. Cybernetics and Systems Analysis. 2012. Vol. 48, N 1. P. 146–156.
72. Rachkovskij D.A. Formation of similarity-reflecting binary vectors with random binary projections.
Cybernetics and Systems Analysis. 2015. Vol. 51, N 2. P. 313–323.
73. Donaldson R., Gupta A., Plan Y., Reimer T. Random mappings designed for commercial search
engines. arXiv:1507.05929. 21 Jul 2015.
74. Ferdowsi S., Voloshynovskiy S., Kostadinov D., Holotyak T. Fast content identification in
highdimensional feature spaces using sparse ternary codes. Proc. WIFS’16. 2016. P. 1–6.
75. Valiant G. Finding correlations in subquadratic time, with applications to learning parities and the
closest pair problem. J. ACM. 2015. Vol. 62, N 2. P. 13:1–13:45.
76. Nguyen H.L. Algorithms for high dimensional data. PhD thesis. Princeton University, 2014. URL:
http://arks.princeton.edu/ark:/88435/dsp01b8515q61f.
77. Rahimi A., Recht B. Random features for large-scale kernel machines. Proc. NIPS’07. 2007.
P. 1177–1184.
78. O’Donnell R., Wu Y., Zhou Y. Optimal lower bounds for locality sensitive hashing (except when
q is tiny). ACM TOCS. 2014. Vol. 6, N 1. P. 5.1–5.13.
79. Wang J., Liu W., Kumar S., Chang S.-F. Learning to hash for indexing big data: A survey. Proc. of
the IEEE. 2016. Vol. 104, N 1. P. 34–57.
80. Wang J., Zhang T., Song J., Sebe N., Shen H.T. A survey on learning to hash. IEEE Trans. PAMI.
doi:10.1109/TPAMI.2017.2699960.
81. Gao L., Song J., Liu X., Shao J., Liu J., Shao J. Learning in high-dimensional multimedia data:
the state of the art. Multimedia Systems. 2017. Vol. 23, N 3. P. 303–313.
82. Mou W., Wang L. A refined analysis of lsh for well-dispersed data points. Proc. ANALCO’17. 2017.
P. 174–182.
83. Andoni A., Indyk P., Nguyen H.L., Razenshteyn I. Beyond locality-sensitive hashing. Proc.
SODA’14. 2014. P. 1018–1028.
84. Andoni A., Razenshteyn I. Tight lower bounds for data-dependent locality-sensitive hashing. Proc.
SoCG’16. 2016. P. 9:1–9:11.
85. Gritsenko V.I., Rachkovskij D.A., Frolov A.A., Gayler R., Kleyko D., Osipov E. Neural distributed
autoassociative memories: A survey. Cybernetics and Computer Engineering. 2017. N 2 (188). P. 5–35.
86. Wang Y., Shrivastava A., Ryu J. FLASH: randomized algorithms accelerated over cpu-gpu for
ultra-high dimensional similarity search. arXiv:1709.01190. 4 Sep 2017.
87. Shrivastava A. Optimal densification for fast and accurate minwise hashing. Proc. ICML’17. 2017.
P. 3154–3163.
Íàä³éøëà äî ðåäàêö³¿ 23.08.2017
Ä.À. Ðà÷êîâñüêèé
²ÍÄÅÊÑͲ ÑÒÐÓÊÒÓÐÈ ÄËß ØÂÈÄÊÎÃÎ ÏÎØÓÊÓ ÇÀ ÑÕÎƲÑÒÞ
IJÉÑÍÈÕ ÂÅÊÒÎвÂ. I
Àíîòàö³ÿ. Íàâåäåíî îãëÿä ³íäåêñíèõ ñòðóêòóð äëÿ øâèäêîãî ïîøóêó çà
ñõîæ³ñòþ îá’ºêò³â, ùî ïðåäñòàâëåí³ ä³éñíèìè âåêòîðàìè. Ðîçãëÿíóòî
³íäåêñí³ ñòðóêòóðè íà îñíîâ³ ëîêàëüíî-÷óòëèâîãî õåøóâàííÿ òà ¿õí³ ìî-
äèô³êàö³¿. Âèêëàäåíî ³äå¿ êîíêðåòíèõ àëãîðèòì³â (â³äîìèõ òà íåùîäàâíî çà-
ïðîïîíîâàíèõ). Îáãîâîðåíî ¿õí³é âçàºìîçâ’ÿçîê ³ äåÿê³ òåîðåòè÷í³ àñïåêòè.
Êëþ÷îâ³ ñëîâà: ïîøóê çà ñõîæ³ñòþ, íàéáëèæ÷èé ñóñ³ä, áëèæí³é ñóñ³ä, ³í-
äåêñí³ ñòðóêòóðè, ëîêàëüíî-÷óòëèâå õåøóâàííÿ, ëîêàëüíî-÷óòëèâà ô³ëüòðàö³ÿ.
D.A. Rachkovskij
INDEX STRUCTURES FOR FAST SIMILARITY SEARCH OF REAL-VALUED VECTORS. I
Abstract. In this survey paper, we consider index structures for fast similarity
search of objects represented by real-valued vectors. Index structures based on
locality-sensitive hashing and their modifications are considered. The ideas of
specific algorithms, including the recently proposed ones, are outlined. Their
interrelations and some theoretical aspects are discussed.
Keywords: similarity search, nearest neighbor, near neighbor, index structures,
locality-sensitive hashing, locality-sensitive filtering.
Ðà÷êîâñêèé Äìèòðèé Àíäðååâè÷,
äîêòîð òåõí. íàóê, âåäóùèé íàó÷íûé ñîòðóäíèê Ìåæäóíàðîäíîãî íàó÷íî-ó÷åáíîãî öåíòðà èíôîð-
ìàöèîííûõ òåõíîëîãèé è ñèñòåì ÍÀÍ Óêðàèíû è ÌÎÍ Óêðàèíû, Êèåâ, e-mail: dar@infrm.kiev.ua.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 1 183
|