Индексные структуры для быстрого поиска по сходству бинарных векторов

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Представлены, главным образом, индексные структуры...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2017
1. Verfasser:	Рачковский, Д.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/144801
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Индексные структуры для быстрого поиска по сходству бинарных векторов / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 167–192. — Бібліогр.: 134 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-144801
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1448012025-02-09T13:28:30Z Индексные структуры для быстрого поиска по сходству бинарных векторов Індексні структури для швидкого пошуку за схожістю бінарних векторів Index structures for fast similarity search of binary vectors Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Представлены, главным образом, индексные структуры на основе хэш-таблиц, сохраняющего сходство хэширования, а также древовидных структур, графов соседства и нейросетевой распределенной автоассоциативной памяти. Изложены идеи известных и предложенных в последнее время алгоритмов. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними векторами (із компонентами 0 або 1). Розглянуто структури як для точного, так і для наближеного пошуку за відстанню Хеммінга та іншими мірами схожості. Описано, головним чином, індексні структури на основі хеш-таблиць, хешування, що зберігає схожість, а також деревовидних структур, графів сусідства та нейромережевої розподіленої автоасоціативної пам’яті. Викладено ідеї конкретних алгоритмів (відомих та нещодавно запропонованих). We survey index structures for fast similarity search of objects represented by binary vectors (with components 0 or 1). Structures for both exact and approximate search by Hamming distance and other similarity measures are considered. Mainly, we present index structures based on hash tables, similarity-preserving hashing, as well as tree structures, neighborhood graphs, and neural distributed autoassociative memory. The ideas of specific algorithms, including the recently proposed ones, are outlined. 2017 Article Индексные структуры для быстрого поиска по сходству бинарных векторов / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 167–192. — Бібліогр.: 134 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144801 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	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рачковский, Д.А. Индексные структуры для быстрого поиска по сходству бинарных векторов Кибернетика и системный анализ
description	Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Представлены, главным образом, индексные структуры на основе хэш-таблиц, сохраняющего сходство хэширования, а также древовидных структур, графов соседства и нейросетевой распределенной автоассоциативной памяти. Изложены идеи известных и предложенных в последнее время алгоритмов.
format	Article
author	Рачковский, Д.А.
author_facet	Рачковский, Д.А.
author_sort	Рачковский, Д.А.
title	Индексные структуры для быстрого поиска по сходству бинарных векторов
title_short	Индексные структуры для быстрого поиска по сходству бинарных векторов
title_full	Индексные структуры для быстрого поиска по сходству бинарных векторов
title_fullStr	Индексные структуры для быстрого поиска по сходству бинарных векторов
title_full_unstemmed	Индексные структуры для быстрого поиска по сходству бинарных векторов
title_sort	индексные структуры для быстрого поиска по сходству бинарных векторов
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2017
topic_facet	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
url	https://nasplib.isofts.kiev.ua/handle/123456789/144801
citation_txt	Индексные структуры для быстрого поиска по сходству бинарных векторов / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 167–192. — Бібліогр.: 134 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT račkovskijda indeksnyestrukturydlâbystrogopoiskaposhodstvubinarnyhvektorov AT račkovskijda índeksnístrukturidlâšvidkogopošukuzashožístûbínarnihvektorív AT račkovskijda indexstructuresforfastsimilaritysearchofbinaryvectors
first_indexed	2025-11-26T05:06:50Z
last_indexed	2025-11-26T05:06:50Z
_version_	1849828167692320768
fulltext	Ä.À. ÐÀ×ÊÎÂÑÊÈÉ ÓÄÊ 004.22 + 004.93’11 ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÁÛÑÒÐÎÃÎ ÏÎÈÑÊÀ ÏÎ ÑÕÎÄÑÒÂÓ ÁÈÍÀÐÍÛÕ ÂÅÊÒÎÐÎÂ Àííîòàöèÿ. Äàí îáçîð èíäåêñíûõ ñòðóêòóð äëÿ áûñòðîãî ïîèñêà ïî ñõîä- ñòâó îáúåêòîâ, ïðåäñòàâëåííûõ áèíàðíûìè âåêòîðàìè (ñ êîìïîíåíòàìè 0 èëè 1). Ðàññìîòðåíû ñòðóêòóðû êàê äëÿ òî÷íîãî, òàê è äëÿ ïðèáëèæåííî- ãî ïîèñêà ïî ðàññòîÿíèþ Õýììèíãà è äðóãèì ìåðàì ñõîäñòâà. Ïðåäñòàâëå- íû, ãëàâíûì îáðàçîì, èíäåêñíûå ñòðóêòóðû íà îñíîâå õýø-òàáëèö, ñîõðàíÿ- þùåãî ñõîäñòâî õýøèðîâàíèÿ, à òàêæå äðåâîâèäíûõ ñòðóêòóð, ãðàôîâ ñîñå- äñòâà è íåéðîñåòåâîé ðàñïðåäåëåííîé àâòîàññîöèàòèâíîé ïàìÿòè. Èçëîæåíû èäåè èçâåñòíûõ è ïðåäëîæåííûõ â ïîñëåäíåå âðåìÿ àëãîðèòìîâ. Êëþ÷åâûå ñëîâà: ïîèñê ïî ñõîäñòâó, ðàññòîÿíèå Õýììèíãà, áëèæàéøèé ñîñåä, áëèæíèé ñîñåä, èíäåêñíûå ñòðóêòóðû, ìóëüòèèíäåêñíîå õýøèðîâà- íèå, ëîêàëüíî-÷óâñòâèòåëüíîå õýøèðîâàíèå, äðåâîâèäíûå ñòðóêòóðû, ãðàô ñîñåäñòâà, íåéðîñåòåâàÿ àâòîàññîöèàòèâíàÿ ïàìÿòü. ÂÂÅÄÅÍÈÅ Ïîèñê ñõîäíûõ ñ îáúåêòîì-çàïðîñîì îáúåêòîâ áàçû ïî íåêîòîðîé ìåðå ðàññòîÿ- íèÿ/ñõîäñòâà íàçûâàþò ïîèñêîì ïî ñõîäñòâó. Íàéäåííûå îáúåêòû (íàïðèìåð, òåêñòû èëè èçîáðàæåíèÿ [1–3]) ìîãóò ÿâëÿòüñÿ êîíå÷íûì ðåçóëüòàòîì ïîèñêà èëè ñîäåðæàòü äîïîëíèòåëüíóþ àññîöèèðîâàííóþ èíôîðìàöèþ î ñõîäíîì ñ íè- ìè âõîäíîì îáúåêòå-çàïðîñå (ñì. ññûëêè â îáçîðå [4]). Â íàñòîÿùåì îáçîðå ðàññìîòðåíî âûïîëíåíèå ïîèñêà ïî ïðåäñòàâëåíèÿì îáúåêòîâ áèíàðíûìè âåêòîðàìè ñ êîìïîíåíòàìè èç { , }0 1 . Ïëîòíûå áèíàðíûå âåêòîðû (ñ ïðè- áëèçèòåëüíî ðàâíûì êîëè÷åñòâîì åäèíè÷íûõ è íóëåâûõ êîìïîíåíòîâ) ìîæíî êîì- ïàêòíî õðàíèòü (òðåáóåòñÿ âñåãî ëèøü îäèí áèò ïàìÿòè íà êîìïîíåíò) è áûñòðî îáðà- áàòûâàòü, îñîáåííî âûïîëíåíèåì ïîêîìïîíåíòíûõ îïåðàöèé, ÷òî èñïîëüçóåòñÿ ïðè âû÷èñëåíèè ìíîãèõ ìåð ðàññòîÿíèÿ/ñõîäñòâà áèíàðíûõ âåêòîðîâ (íàïðèìåð, ðàññòîÿ- íèÿ Õýììèíãà, ïîäðàçä. 1.1). Ðàçðåæåííûå áèíàðíûå âåêòîðû (ñ ìàëîé äîëåé åäèíè÷- íûõ êîìïîíåíòîâ) òàêæå ýôôåêòèâíî õðàíÿòñÿ è îáðàáàòûâàþòñÿ (ïîäðàçä. 1.3). Ïðåäëîæåíû ïðåäñòàâëåíèÿ îáúåêòîâ ðàçëè÷íîãî òèïà â âèäå áèíàðíûõ âåê- òîðîâ, ñõîäñòâî êîòîðûõ îòðàæàåò ñõîäñòâî îáúåêòîâ. Òàêèå áèíàðíûå âåêòîðû ìîæíî ôîðìèðîâàòü íåïîñðåäñòâåííî èç èñõîäíûõ ïðåäñòàâëåíèé îáúåêòîâ. Íàïðèìåð, äëÿ ïðåäñòàâëåíèÿ èçîáðàæåíèé èñïîëüçóþò ïëîòíûå áèíàðíûå âåê- òîðû — ëîêàëüíûå äåñêðèïòîðû ðàçìåðíîñòüþ â ñîòíè áèòîâ (BRIEF, ORB, BRISK, FREAK [5–7] èëè âåêòîðû èç ñëîåâ ãëóáîêèõ íåéðîííûõ ñåòåé [8–10]), ïðèìåíÿþò áèíàðèçàöèþ äèñêðåòíîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ DCT [11] è äð. Òàêèå áèíàðíûå âåêòîðû òàêæå îáúåäèíÿþò â âåêòîðû ðàçìåðíîñòüþ â äå- ñÿòêè òûñÿ÷ áèòîâ. Ðàçðåæåííûå áèíàðíûå âåêòîðû ðàçìåðíîñòüþ â ñîòíè òûñÿ÷ áèòîâ è áîëåå èñïîëüçóþò, íàïðèìåð, äëÿ ïðåäñòàâëåíèÿ ñëîâ [12], èçîáðàæåíèé ëèö [13], äàííûõ î ïîêóïêàõ [14] è äð. Áèíàðíûå âåêòîðû, îòðàæàþùèå ñõîäñòâà îáúåêòîâ, ôîðìèðóþò èç âåêòîðíûõ èëè äðóãèõ ïðåäñòàâëåíèé áåç îáó÷åíèÿ (íàïðèìåð, ñì. îáçîðû â [15–17]) è ñ îáó÷åíèåì [18, 19]. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 167 © Ä.À. Ðà÷êîâñêèé, 2017 Âñëåäñòâèå ýôôåêòèâíîñòè îïåðèðîâàíèÿ áèíàðíûìè âåêòîðàìè äëÿ íå ñëèøêîì áîëüøèõ áàç ìîæåò îêàçàòüñÿ ïðèåìëåìûì äàæå ëèíåéíûé ïîèñê ïî ñõîäñòâó, ò.å. âû÷èñëåíèåì çíà÷åíèé ðàññòîÿíèé/ñõîäñòâ ìåæäó âåêòîðîì-çàïðî- ñîì è âñåìè âåêòîðàìè áàçû. Ñêîðîñòü ëèíåéíîãî ïîèñêà ïîâûøàåòñÿ äëÿ âåêòîðîâ ìàëîé ðàçìåðíîñòè. Â îáçîðå [17] (ñì. òàêæå [20]) ðàññìîòðåíû ìåòîäû ñíèæåíèÿ ðàçìåðíîñòè áèíàðíûõ âåêòîðîâ áåç ó÷èòåëÿ (íàïðèìåð, ñýìïëèðîâàíèå, ñëó÷àéíîå ïðîåöèðî- âàíèå, èñïîëüçîâàíèå LSH è äð.) äëÿ ïîëó÷åíèÿ âåêòîðîâ, ïî êîòîðûì ìîæíî áûñòðåå îöåíèòü ñõîäñòâî èñõîäíûõ. Òàê êàê îöåíêà èñõîäíîãî ñõîäñòâà ïî âåê- òîðàì ñíèæåííîé ðàçìåðíîñòè (â áîëüøèíñòâå ñëó÷àåâ) íåòî÷íàÿ, ðåçóëüòàòû ìîãóò îòëè÷àòüñÿ îò ðåçóëüòàòîâ ëèíåéíîãî ïîèñêà ïî èñõîäíîé ìåðå ñõîäñòâà. Îäíàêî âî ìíîãèõ ñëó÷àÿõ îòëè÷èÿ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà ïðèåìëåìû, åñëè âðåìÿ ïîèñêà óìåíüøàåòñÿ. Äëÿ î÷åíü áîëüøèõ áàç ëèíåéíûé ïîèñê íåäîïóñòèìî ìåäëåííûé. Âîçìîæ- íîñòü ïîèñêà ïî ñõîäñòâó ñ ñóáëèíåéíîé îòíîñèòåëüíî êîëè÷åñòâà îáúåêòîâ â áàçå ñëîæíîñòüþ ïðåäîñòàâëÿþò ñïåöèàëüíûå ñòðóêòóðû äàííûõ — èíäåêñíûå ñòðóêòóðû (ÈÑ), îáåñïå÷èâàþùèå óñêîðåíèå ïîèñêà. Õîòÿ äëÿ áèíàðíûõ âåêòî- ðîâ ìîæíî èñïîëüçîâàòü ÈÑ, ðàáîòàþùèå ñ èíôîðìàöèåé òîëüêî î ðàññòîÿíè- ÿõ [4], èëè ÈÑ äëÿ âåùåñòâåííûõ âåêòîðîâ [21–23], ââèäó ñïåöèôèêè áèíàðíûõ âåêòîðîâ ñïåöèàëèçèðîâàííûå äëÿ íèõ ÈÑ ÷àñòî áîëåå ýôôåêòèâíû. Â íàñòîÿ- ùåì îáçîðå ðàññìîòðåíû òàêèå ÈÑ äëÿ òî÷íîãî è ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó. Ñòðóêòóðà îáçîðà ïðèâåäåíà â ïîäðàçä. 1.6. 1. ÎÑÍÎÂÍÛÅ ÏÎÍßÒÈß 1.1. Ìåðû ðàññòîÿíèÿ è ñõîäñòâà áèíàðíûõ âåêòîðîâ. Äëÿ áèíàðíûõ âåêòî- ðîâ øèðîêî èñïîëüçóþò ðàññòîÿíèå Õýììèíãà dist { }Ham ( , )a b � ��i D i ia b 1 , ãäå D — ðàçìåðíîñòü âåêòîðîâ a , b, { }. — èíäèêàòîðíàÿ ôóíêöèÿ. Äëÿ áèíàð- íûõ âåêòîðîâ ñ êîìïîíåíòàìè èç { , }0 1 âûïîëíÿåòñÿ dist Ham 1( , ) \| \| \| \|a b a b� � � � �\| \| \| \|a b s s, ãäå \| \| \| \| \| \| / a b� � �� s i D i i s s a b 1 1 — ðàññòîÿíèÿ Ìèíêîâñêîãî ðàç- ëè÷íîãî ïîðÿäêà s (íàïðèìåð, äëÿ s � 2 ïîëó÷àåì ðàññòîÿíèå Åâêëèäà). Ýòè ðàññòîÿíèÿ ïðè s � 1 ÿâëÿþòñÿ ìåòðèêàìè, ò.å. ïîä÷èíÿþòñÿ ìåòðè÷åñêèì àêñè- îìàì, òàêèì êàê íåðàâåíñòâî òðåóãîëüíèêà è äð. Äëÿ ñõîäñòâ á�ëüøèå çíà÷åíèÿ ñîîòâåòñòâóþò áîëåå ñõîäíûì îáúåêòàì. Îäíîé èç ìåð ñõîäñòâà âåêòîðîâ ÿâëÿåòñÿ ñêàëÿðíîå ïðîèçâåäåíèå sim dot ( , )a b � � � ��a b, i D i ia b 1 . Êîñèíóñ óãëà ìåæäó âåêòîðàìè îïðåäåëÿåòñÿ êàê cos sim cos( , ) , / (\| \| \| \| \| \| \| \| )a b a b a b� � � 2 2 , ãäå \| \| \| \|z 2 — åâêëèäîâà íîðìà z. Óãîë ìåæäó a, b îïðåäåëÿåò ðàññòîÿíèå dist arccosang � ( , )a b . Äëÿ áèíàðíûõ âåêòîðîâ cos ( , ) , / (\| \| \| \| ) /a b a b a b� � � 1 2 , ãäå \| \|z — êîëè÷åñòâî íåíóëåâûõ êîìïîíåíòîâ âåêòîðà, ò.å. õýììèíãîâà íîðìà. Âûïîëíÿåòñÿ dist Ham ( , ) \| \| \| \| ,a b a b a b� � � � �2 . Ñõîäñòâî Æàêêàðà îïðåäåëÿåòñÿ êàê sim Jac ( , ) , / (\| \| \| \| , )a b a b a b a b� � � � � � � , à ñõîäñòâî Áðàóíà–Áëàíêå — êàê sim BB ( , ) , / max (\| \| , \| \| )a b a b a b� � � . Ýòè ìåðû ÷àñòî èñïîëüçóþò äëÿ ðàçðåæåí- íûõ âåêòîðîâ. Åñëè óïîðÿäî÷èòü (ðàíæèðîâàòü) áàçó áèíàðíûõ âåêòîðîâ ñ ôèê- ñèðîâàííîé õýììèíãîâîé íîðìîé ïî âîçðàñòàíèþ dist Ham èëè dist ang îòíîñè- òåëüíî íåêîòîðîãî âåêòîðà, òàêîé æå ïîðÿäîê ïîëó÷èì óïîðÿäî÷èâàíèåì ïî óáû- âàíèþ sim dot , sim cos, sim Jac, sim BB. Îòìåòèì, ÷òî áèíàðíûå âåêòîðû ìîæíî ðàññìàòðèâàòü êàê õàðàêòåðèñòè÷åñ- êèå âåêòîðû ñîîòâåòñòâóþùèõ íåâçâåøåííûõ ìíîæåñòâ (1 ñîîòâåòñòâóåò íàëè- ÷èþ ýëåìåíòà ìíîæåñòâà, 0 — îòñóòñòâèþ) è âû÷èñëÿòü ïî âåêòîðàì ìåðû ñõî- äñòâà/ðàçëè÷èÿ òàêèõ ìíîæåñòâ. 1.2. Òèïû çàïðîñîâ òî÷íîãî ïîèñêà ïî ñõîäñòâó. Îáúåêòû áàçû, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà êîíêðåòíûé çàïðîñ ïîèñêà ïî ñõîäñòâó, îïðåäåëÿþòñÿ òè- 168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 ïîì çàïðîñà è åãî ïàðàìåòðàìè (îáúåêòîì-çàïðîñîì, ìåðîé ðàññòîÿíèÿ/ñõîäñòâà è äð.). Îáúåêòû-çàïðîñû ìîãóò íå ïðèíàäëåæàòü áàçå. Â íàñòîÿùåì îáçîðå îáú- åêòû ÿâëÿþòñÿ áèíàðíûìè âåêòîðàìè. Äèàïàçîííûé çàïðîñ (range query) îáîçíà÷èì rNN. Îí âîçâðàùàåò îáúåêòû áàçû, ðàññòîÿíèÿ êîòîðûõ îò îáúåêòà-çàïðîñà (ïî ìåðå ðàññòîÿíèÿ, çàäàííîé â çà- ïðîñå) íå ïðåâûøàþò ðàäèóñà çàïðîñà r. Ïðè íåêîòîðûõ r ðåçóëüòàòîì äèàïàçîí- íîãî çàïðîñà ìîæåò áûòü ïóñòîå ìíîæåñòâî îáúåêòîâ èëè âñå îáúåêòû êîíêðåò- íîé áàçû. Â ïîñëåäíåì ñëó÷àå óñêîðåíèå âûïîëíåíèÿ çàïðîñà rNN ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì íåâîçìîæíî â ïðèíöèïå. Ëþáîé îáúåêò, ÿâëÿþùèéñÿ îòâå- òîì íà äèàïàçîííûé çàïðîñ, íàçûâàþò r-áëèæíèì ñîñåäîì (near neighbor), îáîçíà÷èì åãî rNN1. Çàïðîñ rNN1 âîçâðàùàåò òàêîé îáúåêò. Çàïðîñ k áëèæàéøèõ ñîñåäåé (k nearest neighbors, kNN) âîçâðàùàåò k îáúåê- òîâ áàçû, áëèæàéøèõ ê îáúåêòó-çàïðîñó. Çàïðîñ îäíîãî áëèæàéøåãî ñîñåäà, à òàêæå îáúåêò, êîòîðûé ÿâëÿåòñÿ áëèæàéøèì ñîñåäîì, îáîçíà÷èì NN. Çàïðîñ kNN ìîæíî âûïîëíèòü ïîñëåäîâàòåëüíîñòüþ çàïðîñîâ rNN èëè rNN1 ñ óâåëè÷åíèåì r äî òåõ ïîð, ïîêà íå áóäåò äîñòèãíóòî êîëè÷åñòâî k âîçâðà- ùåííûõ îáúåêòîâ. Ìîæíî òàêæå âíà÷àëå ïðèíÿòü r D� / 2 è âûïîëíèòü çàïðîñ rNN1, à çàòåì r D� / 4 èëè r D� 3 4/ (â çàâèñèìîñòè îò íàëè÷èÿ èëè îòñóòñòâèÿ îáúåêòîâ áàçû â ðåçóëüòàòå çàïðîñà) è òàê äàëåå, òîãäà ïîñëå log D çàïðîñîâ ïî- ëó÷àþò NN. Îòìåòèì, ÷òî ìíîãèå îáúåêòû áàçû ìîãóò èìåòü îäèíàêîâîå ðàññòî- ÿíèå äî îáúåêòà-çàïðîñà, îñîáåííî åñëè îáúåêòû — áèíàðíûå âåêòîðû. Çàïðîñû rNN è kNN ñ ïðèâåäåííûìè îïðåäåëåíèÿìè ÿâëÿþòñÿ çàïðîñàìè òî÷íîãî ïîèñêà ïî ñõîäñòâó. Îïðåäåëåíèÿ òèïîâ çàïðîñîâ â òåðìèíàõ íå ðàññòîÿ- íèÿ, à ñõîäñòâà àíàëîãè÷íû. Ñóùåñòâóþò è äðóãèå òèïû çàïðîñîâ òî÷íîãî ïîèñ- êà ïî ñõîäñòâó, îäíàêî â íàñòîÿùåì îáçîðå îíè íå ðàññìàòðèâàþòñÿ. 1.3. Ëèíåéíûé ïîèñê. Âðåìÿ âûïîëíåíèÿ çàïðîñîâ ïîèñêà ïî ñõîäñòâó ëè- íåéíûì ïîèñêîì â áàçå èç N îáúåêòîâ-âåêòîðîâ äëÿ ìåð ðàññòîÿíèÿ/ñõîäñòâà ñ âðåìåíåì âû÷èñëåíèÿ O D( ) (íàïðèìåð, ìåðû äëÿ ïëîòíûõ âåêòîðîâ, ñì. ïîä- ðàçä. 1.1) ñîñòàâëÿåò O ND( ). Äëÿ áèíàðíûõ âåêòîðîâ, êîìïîíåíò êîòîðûõ ïðåäñòàâëåí îäíèì áèòîì (íà- ïðèìåð, 64-ðàçðÿäíîãî ñëîâà), âû÷èñëåíèå dist Ham âûïîëíÿåòñÿ áûñòðûìè ïîáè- òîâûìè îïåðàöèÿìè XOR (îäíîâðåìåííî íàä 64 êîìïîíåíòàìè äâóõ âåêòîðîâ) è ïîäñ÷åòîì êîëè÷åñòâà åäèíè÷íûõ áèòîâ â êàæäîì ïîëó÷èâøåìñÿ ñëîâå. Äëÿ ïîäñ÷åòà ïðèìåíÿþò ëèáî áûñòðûå ñïåöèàëèçèðîâàííûå êîìàíäû ïðîöåññîðà, ëèáî òàáëèöû (íàïðèìåð, äâîè÷íîìó ÷èñëó 11111110 ñîîòâåòñòâóåò ÿ÷åéêà òàá- ëèöû, â êîòîðîé õðàíèòñÿ ÷èñëî 7). Èñïîëüçóþò è èíûå âîçìîæíîñòè ñîâðåìåí- íûõ ïðîöåññîðîâ [24]. Àíàëîãè÷íî âû÷èñëÿþòñÿ äðóãèå ìåðû ðàññòîÿíèÿ/ñõî- äñòâà áèíàðíûõ âåêòîðîâ èç ïîäðàçä. 1.1. Âðåìÿ âû÷èñëåíèé ïî ñðàâíåíèþ ñ âåùåñòâåííûìè âåêòîðàìè ìîæåò ñîêðàòèòüñÿ â äåñÿòêè ðàç. Äëÿ ðàçðåæåííûõ áèíàðíûõ âåêòîðîâ èñïîëüçóþò ïðåäñòàâëåíèå â âèäå íî- ìåðîâ íåíóëåâûõ êîìïîíåíòîâ. Âðåìÿ âû÷èñëåíèÿ ìåðû ðàññòîÿíèÿ/ñõîäñòâà ïðîïîðöèîíàëüíî ñóììàðíîìó êîëè÷åñòâó íåíóëåâûõ êîìïîíåíòîâ â äâóõ âåêòî- ðàõ. Ïðèìåíÿþò òàêæå ñïåöèàëèçèðîâàííûå àëãîðèòìû (ïîäðàçä. 1.4.3) è ñðåäñòâà ([25] è ïîäðàçä. 5.1 â [17]). 1.4. Áàçîâûå èíäåêñíûå ñòðóêòóðû äëÿ óñêîðåíèÿ òî÷íîãî ïîèñêà ïî ñõîäñòâó. 1.4.1. Òî÷íûé ïîèñê â øàðå Õýììèíãà ìîäèôèêàöèåé âåêòîðà çàïðîñà. Îñîáåííîñòüþ áèíàðíûõ âåêòîðîâ ÿâëÿåòñÿ âîçìîæíîñòü èõ íåïîñðåäñòâåííîãî èñïîëüçîâàíèÿ â êà÷åñòâå àäðåñîâ ÿ÷ååê (êîðçèí) õýø-òàáëèö. Ïðîñòîé àëãîðèòì âûïîëíåíèÿ çàïðîñà rNN ïî dist Ham (íàïðèìåð, [26]) êîíñòðóèðóåò òàáëèöó, â êîòîðîé êàæäûé áèíàðíûé âåêòîð áàçû ïîìåùàåòñÿ â ÿ÷åéêó ñ íîìåðîì, ñîîò- âåòñòâóþùèì åãî áèíàðíîìó êîäó (òàê, âåêòîðó 1111 ñîîòâåòñòâóåò ÿ÷åéêà ñ íî- ìåðîì 15). Íàëè÷èå â áàçå âåêòîðà, ñîâïàäàþùåãî ñ çàïðîñîì, îïðåäåëÿåòñÿ ïðî- âåðêîé çàïîëíåííîñòè ñîîòâåòñòâóþùåé ÿ÷åéêè, ò.å. çà ïîñòîÿííîå âðåìÿ O( )1 . Äëÿ çàïðîñà rNN âûïîëíÿþò ñèñòåìàòè÷åñêóþ ìîäèôèêàöèþ âåêòîðà-çàïðîñà, ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 169 èçìåíÿÿ (0 íà 1 è 1 íà 0) çíà÷åíèÿ r åãî êîìïîíåíòîâ òàê, ÷òîáû ïîëó÷èòü âñå âåêòîðû, ëåæàùèå âíóòðè øàðà Õýììèíãà ñ ðàäèóñîì r è öåíòðîì â âåêòîðå-çà- ïðîñå (ò.å. ëåæàùèå íà ñôåðàõ Õýììèíãà ñ ðàäèóñàìè îò 0 äî r). Ìîäèôèêàöèè èñïîëüçóþò â êà÷åñòâå çàïðîñîâ äëÿ ïîèñêà ïî ñîâïàäåíèþ. Íàïðèìåð, äëÿ âåê- òîðà 1111 ìîäèôèêàöèÿìè ïðè r �1 ÿâëÿþòñÿ {0111, 1011, 1101, 1110}. Ïðåèìóùåñòâà òàêîé ÈÑ — ïðîñòîòà êîíñòðóèðîâàíèÿ, âîçìîæíîñòü âûïîë- íåíèÿ çàïðîñîâ rNN ñ èçìåíÿåìûì ðàäèóñîì è áûñòðûé ïîèñê äëÿ ìàëûõ r, à îäèí èç íåäîñòàòêîâ — çàòðàòû ïàìÿòè 2D è åå íåðàöèîíàëüíîå èñïîëüçîâàíèå ïðè N D�� 2 (áîëüøèíñòâî ÿ÷ååê ïóñòûå). Óñòðàíèòü ýòîò íåäîñòàòîê ìîæíî ñî- ðòèðîâêîé âåêòîðîâ áàçû â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå (0 ïðåäøåñòâóåò 1, ÷òî ýêâèâàëåíòíî ñîðòèðîâêå ïî âåëè÷èíå ñîîòâåòñòâóþùèõ öåëûõ ÷èñåë) è çàïîìè- íàíèåì â N ÿ÷åéêàõ. Ñîâïàäàþùèé ñ çàïðîñîì âåêòîð íàõîäÿò ïîèñêîì äèõîòî- ìèåé, âðåìÿ êîòîðîãî â õóäøåì ñëó÷àå O N( )log [4]. Âðåìÿ O D( ) ïîëó÷àþò ïðè ïîèñêå ñîâïàäåíèÿ ïîêîìïîíåíòíûìè ñðàâíåíèÿìè. Äðóãîé âàðèàíò óñîâåðøåíñòâîâàíèÿ òàêîé ÈÑ ñîñòîèò â èñïîëüçîâàíèè óíèâåðñàëüíîãî õýøèðîâàíèÿ [27] è ñîçäàíèè õýøåé ðàçìåðíîñòüþ log N . Ýòî äàåò ñðåäíåå âðåìÿ äîñòóïà O( )1 . Èäåàëüíîå õýøèðîâàíèå [28] (õýøè íå èìåþò êîëëèçèé äëÿ ðàçëè÷íûõ îáúåêòîâ áàçû) èñõîäíûõ âåêòîðîâ äàåò âðåìÿ äîñòóïà O( )1 â õóäøåì ñëó÷àå çà ñ÷åò çàòðàò ïàìÿòè O N( ) íà õðàíåíèå èäåàëüíîé õýø-ôóíêöèè äëÿ êîíêðåòíîé áàçû. Íà ïðàêòèêå èäåàëüíîå õýøèðîâàíèå ïðèâîäèò ê çíà÷èòåëüíûì íàêëàäíûì ðàñõîäàì [29]. Îñíîâíûì íåäîñòàòêîì ðàññìàòðèâàåìîé ÈÑ ÿâëÿåòñÿ êîëè÷åñòâî i r D iC�� 0 ìîäèôèêàöèé âåêòîðà çàïðîñà, ÷òî ïðåâûøàåò ( / )D r r [30]. Ýòî ÷èñëî ìîæåò ïðåâûñèòü ðàçìåð áàçû N , ÷òî äåëàåò òàêóþ ÈÑ íåïðèãîäíîé äëÿ ïðàêòè÷åñêîãî ïðèìåíåíèÿ ïðè áîëüøèõ D è r. Èñïîëüçîâàíèå çàïðîñîâ ïîèñêà íå ïî ñîâïàäå- íèþ, à ñ åäèíè÷íûì ðàäèóñîì (ïîäðàçä. 2.1) ïîçâîëÿåò âûïîëíÿòü çàïðîñ â r ðàç áûñòðåå ïðè çàòðàòàõ ïàìÿòè O ND( ), ÷òî íå ðåøàåò ïðîáëåìû. 1.4.2. Èíäåêñíûå ñòðóêòóðû ñ ýêñïîíåíöèàëüíûìè çàòðàòàìè ïàìÿòè. Â ÈÑ äëÿ âûïîëíåíèÿ çàïðîñà NN [31] äëÿ âñåõ âîçìîæíûõ 2D âåêòîðîâ-çàïðî- ñîâ ïðè êîíñòðóèðîâàíèè çàïîìèíàþò òî÷íîãî NN. Äëÿ âûïîëíåíèÿ çàïðîñà rNN â ÈÑ ìîæíî çàïîìíèòü âñå âåêòîðû áàçû, íàõîäÿùèåñÿ íà ðàññòîÿíèè äî r îò èñ- õîäíûõ. Ýòî óâåëè÷èâàåò çàòðàòû ïàìÿòè â i r D iC�� 0 ðàç. Òàêèå ÈÑ íåïðàêòè÷- íû âñëåäñòâèå ýêñïîíåíöèàëüíûõ îò D çàòðàò ïàìÿòè. 1.4.3. Îáðàòíûé èíäåêñ. Êëàññè÷åñêîå îáðàòíîå èíäåêñèðîâàíèå ïðèìåíÿ- þò äëÿ áûñòðîãî âû÷èñëåíèÿ sim dot ðàçðåæåííûõ âåêòîðîâ áàçû è çàïðîñà [32, 33, 25, 34], â òîì ÷èñëå è äëÿ áèíàðíûõ èëè òåðíàðíûõ âåêòîðîâ [33, 25, 34]. Ñõîäíîå ðåøåíèå èñïîëüçóþò â ïîèñêîâûõ ñèñòåìàõ Èíòåðíåòà [32, 25]. Äëÿ êàæäîãî êîìïîíåíòà âåêòîðà çàïîìèíàþò ñïèñîê îáúåêòîâ áàçû, äëÿ êî- òîðûõ ýòîò êîìïîíåíò èìååò íåíóëåâîå çíà÷åíèå, è çíà÷åíèÿ êîìïîíåíòà â ýòèõ îáúåêòàõ. Äëÿ ïîëó÷åíèÿ sim dot âåêòîðà-çàïðîñà ñ âåêòîðàìè áàçû âû÷èñëÿþò ïðîèçâåäåíèÿ íåíóëåâûõ êîìïîíåíòîâ âåêòîðà-çàïðîñà è çàïîìíåííûõ çíà÷åíèé â ñîîòâåòñòâóþùèõ èì ñïèñêàõ îáúåêòîâ è ñóììèðóþò ïðîèçâåäåíèÿ, ñîîòâå- òñòâóþùèå êàæäîìó ïîñåùåííîìó îáúåêòó áàçû. Åñëè êîëè÷åñòâî ïîñåùåííûõ îáúåêòîâ ìåíüøå N , ïîëó÷èì ñóáëèíåéíîå âðåìÿ (ëèøü ýòè îáúåêòû ïîäëåæàò ðàíæèðîâàíèþ). Êðîìå òîãî, ñîêðàùåíèÿ âðåìåíè âû÷èñëåíèé äîñòèãàþò çà ñ÷åò îáðàáîòêè òîëüêî íåíóëåâûõ êîìïîíåíòîâ âåêòîðîâ. Ïîýòîìó îáðàòíûé èíäåêñ îñîáåííî ýôôåêòèâåí äëÿ âåêòîðîâ ñ ìàëûì êîëè÷åñòâîì íåíóëåâûõ êîìïîíåí- òîâ ïðè ìàëîì êîëè÷åñòâå ïîñåùåííûõ îáúåêòîâ. Àíàëîãè÷íî âû÷èñëÿþò äðóãèå ìåðû, èñïîëüçóþùèå sim dot (ñì. ïîäðàçä. 1.1). 1.5. Ïåðåõîä îò òî÷íîãî ê ïðèáëèæåííîìó ïîèñêó. Äëÿ àëãîðèòìîâ, ðàñ- ñìîòðåííûõ â ïîäðàçä. 1.4.1 è 1.4.2, çàòðàòû ïàìÿòè èëè âðåìåíè ðàñòóò ýêñïîíåí- öèàëüíî îò D èëè r. Áîëåå òîãî, àíàëèç âñåõ èçâåñòíûõ àëãîðèòìîâ òî÷íîãî âûïîë- íåíèÿ çàïðîñà NN ñ ñóáëèíåéíûì îò N âðåìåíåì ïîêàçûâàåò, ÷òî çàòðàòû ïàìÿòè 170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 èëè âðåìåíè ðàñòóò ýêñïîíåíöèàëüíî îò D [31]. Äëÿ àëãîðèòìîâ ñ çàòðàòàìè ïàìÿ- òè, áëèçêèìè ê ëèíåéíûì, ëó÷øåå èçâåñòíîå âðåìÿ min ( , )( )2O D DN [31]. Ïîýòî- ìó äëÿ áàç ñ äîñòèæèìûì N òî÷íûé ïîèñê âûðîæäàåòñÿ â ëèíåéíûé ñ ðîñòîì D, äàæå ïðè íå ñëèøêîì áîëüøèõ D, ÷òî ïîäòâåðæäàåòñÿ è íà ïðàêòèêå [35]. Ñîãëàñíî ïðåäïîëîæåíèþ «ïðîêëÿòèÿ ðàçìåðíîñòè» [31] òàêàÿ çàâèñèìîñòü íåèçáåæíà ïðè òî÷íîì ïîèñêå ïî ñõîäñòâó äëÿ äàííûõ õóäøåãî ñëó÷àÿ (äëÿ îáú- åêòà-çàïðîñà è îáúåêòîâ áàçû, êîòîðûå äàþò íàèáîëüøåå âðåìÿ âûïîëíåíèÿ çà- ïðîñà). Äëÿ íåêîòîðûõ àëãîðèòìîâ ýêñïîíåíöèàëüíàÿ çàâèñèìîñòü ïðîÿâëÿåòñÿ â òåðìèíàõ «âíóòðåííåé» ðàçìåðíîñòè (ñì. ññûëêè â [4]), êîòîðàÿ ìîæåò áûòü ìåíüøå «âíåøíåé» ðàçìåðíîñòè D [36]. Îòìåòèì èñêëþ÷åíèå äëÿ ñïåöèàëüíîãî ñëó÷àÿ D O N� (log ) è îáðàáîòêè N çàïðîñîâ (õóäøåãî ñëó÷àÿ): äëÿ êàæäîãî çà- ïðîñà ïîëó÷àþò (ðàíäîìèçèðîâàííîå, ñ âûñîêîé âåðîÿòíîñòüþ) ñóáëèíåéíîå âðåìÿ íàõîæäåíèÿ òî÷íîãî NN äëÿ ðÿäà ðàññòîÿíèé/ñõîäñòâ [37]. Ïðåîäîëåòü (òî÷íåå, îáîéòè) ïðîêëÿòèå ðàçìåðíîñòè óäàåòñÿ ïåðåõîäîì îò òî÷íîãî ê áîëåå áûñòðîìó, íî ïðèáëèæåííîìó ïîèñêó, êîòîðûé äîïóñêàåò îòëè- ÷èå ðåçóëüòàòîâ îò òî÷íîãî ïîèñêà. Ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó âîñòðåáî- âàí íà ïðàêòèêå, ïîñêîëüêó äëÿ ìíîãèõ ïðèìåíåíèé äîñòàòî÷íî ïîëó÷àòü ïðèáëèæåííûå ðåçóëüòàòû, íî áûñòðî. Äëÿ àëãîðèòìîâ ïðèáëèæåííîãî ïîèñêà ñ êîëè÷åñòâåííûìè ãàðàíòèÿìè ðàñ- ñìàòðèâàþò äâà òèïà îòëè÷èé èõ ðåçóëüòàòîâ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà. Â ñëó÷àå äåòåðìèíèðîâàííûõ ïðèáëèæåííûõ àëãîðèòìîâ ðàññòîÿíèå äî íàéäåí- íûõ îáúåêòîâ íå áîëåå ÷åì íà çàäàííûé ìíîæèòåëü ïðåâûøàåò ðàññòîÿíèå äî îáú- åêòîâ, êîòîðûå ÿâëÿþòñÿ òî÷íûì îòâåòîì íà çàïðîñ. Â ñëó÷àå ðàíäîìèçèðîâàí- íûõ àëãîðèòìîâ (òî÷íûõ èëè ïðèáëèæåííûõ) òèïà Monte Carlo (ò.å. ñ îãðàíè÷åí- íûì âðåìåíåì ðàáîòû, íî ñ íåêîòîðîé âåðîÿòíîñòüþ íåêîððåêòíîãî îòâåòà) äëÿ ïîèñêà ïî ñõîäñòâó äîïóñêàþòñÿ false negatives (àëãîðèòì ìîæåò íå âîçâðàòèòü îáúåêòû, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà çàïðîñ). Ïðèáëèæåííûå ðàíäîìèçèðîâàííûå àëãîðèòìû (ò.å. äîïóñêàþùèå îáà òèïà îòëè÷èé: ïðèáëèæåííîñòü è âåðîÿòíîñòü îøèáêè) îáû÷íî èìåþò ëó÷øèå õàðàê- òåðèñòèêè, ÷åì àëãîðèòìû, äîïóñêàþùèå îäèí òèï îòëè÷èé: ëèáî ïðèáëèæåíèå, ëèáî âåðîÿòíîñòü îøèáêè [31]. Â ðàçä. 3 ðàññìîòðåíû òèïû çàïðîñîâ äëÿ ïðèáëè- æåííîãî ïîèñêà ñî ñïåöèôèöèðîâàííûìè ïðèáëèæåíèåì è âåðîÿòíîñòüþ îøèá- êè, à òàêæå àëãîðèòìû Monte Carlo èõ âûïîëíåíèÿ ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè äëÿ äàííûõ õóäøåãî ñëó÷àÿ, âêëþ÷àÿ ïðàêòè÷åñêè ðåàëèçóåìûå. Ñ ïîìîùüþ ðàíäîìèçèðîâàííûõ àëãîðèòìîâ òèïà Las Vegas çàïðîñû ïîèñêà ïî ñõîäñòâó (òî÷íîãî èëè ïðèáëèæåííîãî) âûïîëíÿþò áåç false negatives, îäíàêî ñóáëèíåéíîå âðåìÿ îáåñïå÷èâàåòñÿ ëèøü äëÿ ñðåäíåãî ñëó÷àÿ (âåêòîðû áàçû è çàïðîñîâ âûáðàíû ñëó÷àéíî è íåçàâèñèìî èç èõ ðàñïðåäåëåíèé). Äëÿ äàííûõ õóäøåãî ñëó÷àÿ âðåìÿ çàïðîñà ìîæåò ñòàíîâèòüñÿ ðàâíûì (è áîëüøèì) âðåìåíè ëèíåéíîãî ïîèñêà. Àëãîðèòìû Las Vegas äëÿ òî÷íîãî ïîèñêà ïðèâåäåíû â ðàçä. 2 è äëÿ ïðèáëèæåííîãî ïîèñêà — â ïîäðàçä. 3.6. Íà ïðàêòèêå ïîëüçîâàòåëåé ÷àñòî èíòåðåñóþò íå òåîðåòè÷åñêèå ãàðàíòèè, à âðåìÿ âûïîëíåíèÿ çàïðîñîâ â ýêñïåðèìåíòàõ íà êîíêðåòíûõ áàçàõ. Ýòî âðåìÿ îáû÷íî çàâèñèò îò âûáîðà ïàðàìåòðîâ ÈÑ. Äëÿ òî÷íîãî ïîèñêà ëó÷øåé ÿâëÿåòñÿ ÈÑ, îáåñïå÷èâàþùàÿ íàèìåíüøèå çàòðàòû âðåìåíè. Äëÿ ïðèáëèæåííîãî ïîèñêà âûáîð ïàðàìåòðîâ ÈÑ îáû÷íî ïîçâîëÿåò äîñ- òè÷ü íåêîòîðîãî êîìïðîìèññà ìåæäó êà÷åñòâîì ðåçóëüòàòîâ ïîèñêà (ñòåïåíüþ èõ îòëè÷èÿ îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà) è âðåìåíåì ïîèñêà. Ïîýòîìó ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ñðàâíèâàþò ïî (óñðåäíåííîìó) âðåìåíè âûïîëíåíèÿ çà- ïðîñà ïðè ôèêñèðîâàííîì êà÷åñòâå ïîèñêà èëè ïî çíà÷åíèþ ìåðû êà÷åñòâà ïîèñ- êà ïðè îäèíàêîâîì âðåìåíè ïîèñêà. Âàæíîé õàðàêòåðèñòèêîé òàêæå ÿâëÿþòñÿ çàòðàòû ïàìÿòè ÈÑ (êâàäðàòè÷íûå çàòðàòû îáû÷íî íåïðèåìëåìû). ×àñòî èñïîëüçóþò ìåðû êà÷åñòâà âûïîëíåíèÿ êîíêðåòíîãî çàïðîñà, èçâåñ- òíûå êàê [38] ïîëíîòà (recall), ðàâíàÿ n n1 2/ , è òî÷íîñòü (precision), ðàâíàÿ n n1 3/ , ãäå n1 — êîëè÷åñòâî âîçðàùåííûõ îáúåêòîâ, ñîâïàâøèõ ñ ðåëåâàíòíûìè, n2 — ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 171 êîëè÷åñòâî ðåëåâàíòíûõ çàïðîñó îáúåêòîâ â áàçå, n3 — êîëè÷åñòâî âîçðàùåííûõ îáúåêòîâ áàçû. Äëÿ çàïðîñà kNN n n k2 3� � , ïîýòîìó òî÷íîñòü ðàâíà ïîëíîòå. «Õîðîøèìè» ñîñåäÿìè ìîãóò áûòü íå òîëüêî òî÷íûå ñîñåäè, íî è îáúåêòû áàçû, áëèçêèå ê òî÷íûì ñîñåäÿì. Ïîýòîìó êà÷åñòâî ïîèñêà òàêæå èçìåðÿþò îòíîøåíè- åì ñóììû (èëè ñðåäíåãî) ðàññòîÿíèé îáúåêòà-çàïðîñà äî âîçâðàùåííûõ îáúåêòîâ ê ñîîòâåòñòâóþùåé âåëè÷èíå äëÿ òî÷íîãî ðåçóëüòàòà. Ïðè âûïîëíåíèè ìíîæåñòâà çàïðîñîâ ïîëó÷åííûå äëÿ èíäèâèäóàëüíûõ çàïðîñîâ çíà÷åíèÿ ìåð êà÷åñòâà óñðåäíÿþò. Òàê, äëÿ çàïðîñà NN ïîëíîòó (ðàâíóþ òî÷íîñòè) èçìåðÿþò êàê ïðîöåíò çàïðîñîâ, äëÿ êîòîðûõ áûë âîçâðàùåí òî÷íûé NN [39]. 1.6. Òèïû ðàññìîòðåííûõ â îáçîðå èíäåêñíûõ ñòðóêòóð. Ìíîãèå àëãîðèò- ìû óñêîðåíèÿ ïîèñêà ïî ñõîäñòâó, ïðèâåäåííûå â îáçîðå, ïðèìåíÿþò äâóõýòàï- íóþ ñòðàòåãèþ ôèëüòðàöèè è óòî÷íåíèÿ (filter-and-refine, F&R). Íà ïåðâîì ýòàïå îñóùåñòâëÿåòñÿ áûñòðûé îòáîð îáúåêòîâ-êàíäèäàòîâ. Ðåçóëüòàòû ïåðâîãî ýòàïà óòî÷íÿþòñÿ íà âòîðîì ýòàïå (îáû÷íî ñ èñïîëüçîâàíèåì ëèíåéíîãî ïîèñêà ñðåäè îáúåêòîâ-êàíäèäàòîâ ïî ìåðå ðàññòîÿíèÿ/ñõîäñòâà, çàäàííîé â çàïðîñå). Ñòðàòå- ãèþ F&R èíîãäà ïðèìåíÿþò ìíîãîêðàòíî ïðè âûïîëíåíèè îäíîãî çàïðîñà. Îòìåòèì, ÷òî äëÿ çàïðîñà rNN âòîðîé ýòàï óñòðàíÿåò false positives. Áîëüøèíñòâî ÈÑ, ðàññìîòðåííûõ â ðàçä. 2 è 3, èñïîëüçóþò ìíîæåñòâî õýø-òàáëèö. Â ðàçä. 2 ïðèâåäåíû ÈÑ äëÿ òî÷íîãî ïîèñêà ïî dist Ham ñ ãàðàíòèÿ- ìè ñóáëèíåéíîãî âðåìåíè äëÿ õóäøåãî ñëó÷àÿ ïðè î÷åíü ìàëûõ ðàäèóñàõ, à â îñíîâíîì ñ ãàðàíòèÿìè äëÿ ñðåäíåãî ñëó÷àÿ. Â ðàçä. 3 ðàññìîòðåíû ÈÑ íà îñíîâå LSH-õýøèðîâàíèÿ äëÿ dist Ham è äðóãèõ ìåð ðàññòîÿíèÿ/ñõîäñòâà, äëÿ êî- òîðûõ ñóùåñòâóþò LSH-ôóíêöèè. Ýòè ÈÑ îáåñïå÷èâàþò ãàðàíòèè õóäøåãî ñëó- ÷àÿ äëÿ íåêîòîðûõ òèïîâ çàïðîñîâ ïðèáëèæåííîãî âåðîÿòíîñòíîãî ïîèñêà. Â ðàçä. 4 è 5 ïðåäñòàâëåíû ñîîòâåòñòâåííî ÈÑ íà îñíîâå äåðåâüåâ è ãðàôîâ ñî- ñåäñòâà â îñíîâíîì äëÿ ïðèáëèæåííîãî ïîèñêà áåç ñòðîãèõ ãàðàíòèé. Â ðàçä. 6. ðàññìîòðåíû ÈÑ íà îñíîâå ðàñïðåäåëåííîé íåéðîñåòåâîé àññîöèàòèâíîé ïàìÿòè, ãëàâíûì îáðàçîì, ñ àñèìïòîòè÷åñêèìè ãàðàíòèÿìè (ïðè ðàçìåðíîñòè, ñòðåìÿ- ùåéñÿ ê áåñêîíå÷íîñòè) äëÿ ñëó÷àéíûõ ðàçðåæåííûõ âåêòîðîâ. 2. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÒÎ×ÍÎÃÎ ÏÎÈÑÊÀ ÏÎ ÐÀÑÑÒÎßÍÈÞ ÕÝÌÌÈÍÃÀ Äëÿ âûïîëíåíèÿ òî÷íîãî çàïðîñà rNN ïî dist Ham ïðèìåíÿþò ÈÑ â îñíîâíîì ñ èñïîëüçîâàíèåì õýø-òàáëèö. Äàëåå ïðèâåäåíû ÈÑ ñ ãàðàíòèÿìè õóäøåãî ñëó÷àÿ äëÿ åäèíè÷íîãî è äðóãèõ ìàëûõ ôèêñèðîâàííûõ ðàäèóñîâ çàïðîñà (ïîäðàçä. 2.1), à òàêæå ñ ãàðàíòèÿìè ñðåäíåãî ñëó÷àÿ äëÿ ôèêñèðîâàííîãî è èçìåíÿåìîãî ðàäèóñà (ïîäðàçä. 2.2). 2.1. Èíäåêñíûå ñòðóêòóðû äëÿ òî÷íîãî ïîèñêà ñ ãàðàíòèÿìè õóäøåãî ñëó÷àÿ. 2.1.1. Åäèíè÷íûé ðàäèóñ. Âûïîëíåíèå çàïðîñà rNN ïî dist Ham äëÿ r �1 ìî- äèôèêàöèåé çàïðîñà (ñì. ïîäðàçä. 1.4.1) òðåáóåò âûïîëíåíèÿ D �1 çàïðîñîâ íà ñîâïàäåíèå (â òåðìèíàõ D-êîìïîíåíòíûõ âåêòîðîâ). Ðàçðàáîòàíû óñîâåðøåí- ñòâîâàíèÿ ýòîãî àëãîðèòìà. Â [40] ðåøàþò ñëåäóþùóþ çàäà÷ó: îïðåäåëèòü íàëè÷èå â áàçå âåêòîðà íà ðàñ- ñòîÿíèè r � 1 îò âåêòîðà-çàïðîñà, ò.å. áëèæíåãî ñîñåäà rNN1. Âûÿâëåíèå ñîâïàäå- íèÿ (r � 0) è îáðàáîòêà «ïëîõèõ» âåêòîðîâ-çàïðîñîâ âûïîëíÿþòñÿ ñ èñïîëüçîâàíè- åì õýøèðîâàíèÿ âåêòîðîâ ïîëíîé ðàçìåðíîñòè. Äëÿ r �1, åñëè ðàçáèòü âåêòîðû íà äâå ÷àñòè, òî â îäíîé âåêòîð-çàïðîñ ñîâïàäåò ñ âåêòîðàìè-êàíäèäàòàìè áàçû, ñðå- äè êîòîðûõ íàõîäÿòñÿ âåêòîðû, ÿâëÿþùèåñÿ îòâåòîì íà çàïðîñ, à â äðóãîé — áó- äåò îòëè÷àòüñÿ â îäíîì êîìïîíåíòå. Äëÿ âåêòîðîâ-êàíäèäàòîâ ñ ñîâïàâøåé ÷àñòüþ íåñîâïàâøóþ ðåêóðñèâíî ðàçáèâàþò íà äâå ÷àñòè, ïîêà îäíà èç íèõ íå ñòàíåò êîì- ïîíåíòîì èëè êîëè÷åñòâî êàíäèäàòîâ íå óìåíüøèòñÿ äî îäíîãî. Äëÿ âûÿâëåíèÿ ñîâïàäàþùèõ ÷àñòåé âåêòîðîâ óáûâàþùåé ðàçìåðíîñòè è ñîîòâåòñòâóþùèõ ïîä- ìíîæåñòâ êàíäèäàòîâ ïðè âûïîëíåíèè çàïðîñà äëÿ âåêòîðîâ áàçû ïðåäâàðèòåëüíî êîíñòðóèðóþò ÈÑ íà îñíîâå õýø-òàáëèö (äëÿ ÷àñòåé âäâîå óáûâàþùåé ðàçìåðíîñ- òè è ìíîæåñòâ âåêòîðîâ áàçû óáûâàþùåé ìîùíîñòè). Äëÿ ìîäåëè bit probe, â êîòî- ðîé ñëîæíîñòü èçìåðÿåòñÿ òîëüêî êîëè÷åñòâîì áèòîâûõ äîñòóïîâ ê ïàìÿòè ÈÑ 172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 (äîñòóï âîçâðàùàåò îäèí áèò), çàòðàòû ïàìÿòè ñîñòàâëÿþò O DN D( log ), âðåìÿ ðåøåíèÿ çàäà÷è O D N( log log ). Ìîäèôèêàöèÿ ýòîé ÈÑ âûïîëíÿåò è çàïðîñ rNN. Â [26] ïðèìåíÿþò ìîäåëü RAM (random access machine), â êîòîðîé âðåìÿ çà- ïðîñà âêëþ÷àåò êàê îïåðàöèè äîñòóïà, òàê è òðåáóþùèåñÿ àðèôìåòè÷åñêèå îïå- ðàöèè. Èñïîëüçîâàíèå ïðåôèêñíûõ äåðåâüåâ ñ ëåêñèêîãðàôè÷åñêè óïîðÿäî÷åí- íûìè âåêòîðàìè ïîçâîëèëî ïðè çàòðàòàõ ïàìÿòè O DN( ) äîñòè÷ü âðåìåíè O D( ) ïîëó÷åíèÿ ðåøåíèÿ î ñóùåñòâîâàíèè rNN1 â áàçå è âîçâðàùåíèÿ âñåõ òàêèõ âåêòîðîâ (êîëè÷åñòâî êîòîðûõ íå ïðåâûøàåò D �1). Â ðàáîòå [41] äëÿ âñåõ D îäíîêîìïîíåíòíûõ ìîäèôèêàöèé êàæäîãî âåêòîðà áàçû êîíñòðóèðóþò èäåàëüíóþ ôóíêöèþ õýøèðîâàíèÿ [28]. Â êàæäîé èç O DN( ) ÿ÷å- åê òàáëèöû çàïîìèíàþò íîìåð ìîäèôèöèðîâàííîãî êîìïîíåíòà, ÷òî òðåáóåò log D áèòîâ, îáùèå çàòðàòû ïàìÿòè O DN D( log ) áèòîâ. Ïðè âûïîëíåíèè çàïðîñà âû÷èñëÿ- þò õýø âåêòîðà-çàïðîñà, èçâëåêàþò èç òàáëèöû íîìåð èñêàæåííîãî êîìïîíåíòà, èí- âåðòèðóþò åãî â âåêòîðå-çàïðîñå è ïðîâåðÿþò ñîâïàäåíèå ñ âåêòîðîì áàçû. Åñëè ñî- âïàäåíèå ñóùåñòâóåò, òî ïîëó÷àþò îòâåò, â ïðîòèâíîì ñëó÷àå dist Ham �1. Äëÿ ìîäåëè ñell probe (àíàëîã bit probe ñ äîñòóïîì ê ìàøèííûì ñëîâàì ðàçìåðíîñòüþ D) çàòðàòû ïàìÿòè ñîñòàâëÿþò O N D( log ) ïðè âðåìåíè O( )1 âûïîëíåíèÿ çàïðîñà rNN1. 2.1.2. Èíäåêñíûå ñòðóêòóðû ñ ôèêñèðîâàííûì ðàäèóñîì çàïðîñà r � 1. Çàäà÷à ñî- çäàíèÿ ÈÑ äëÿ âûïîëíåíèÿ òî÷íûõ çàïðîñîâ rNN ïðè r �1 ñ ãàðàíòèÿìè äëÿ äàííûõ õóäøåãî ñëó÷àÿ î÷åíü ñëîæíà. Ïðîñòàÿ ÈÑ ñ ìîäèôèêàöèåé çàïðîñà (ñì. ïîäðàçä. 1.4.1) ïîçâîëÿåò ðàáîòàòü è ñ èçìåíÿåìûì r, íî óñêîðåíèå ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì íà ïðàêòèêå âîçìîæíî òîëüêî ïðè ìàëûõ D è r. Â [42] äëÿ çàïðîñà rNN ñ ôèêñèðîâàí- íûì r ïðåäëîæåíà ÈÑ k-errata trie, êîòîðàÿ âêëþ÷àåò ñóôôèêñíîå äåðåâî è ñòðóêòóðó íàèáîëüøåãî îáùåãî ïðåôèêñà. Çàòðàòû ïàìÿòè O DN N c N rr( ( log ) / !)� 1 , âðå- ìÿ çàïðîñà O D c N r DNr( (( log ) / !) log log( ) )� �2 occ , ãäå c1, c2 0� — êîíñòàíòû, occ — êîëè÷åñòâî âåêòîðîâ áàçû, ÿâëÿþùèõñÿ îòâåòîì íà çàïðîñ. Äëÿ ëèíåéíûõ çàòðàò ïàìÿòè ïîëó÷åíî âðåìÿ O D( � �occ (log ) loglog )( )N Nr r�1 [43] è O D N Nr( log log log )� �1 occ [44]. Òàêèå ÈÑ [42–44] íåëüçÿ èñïîëüçîâàòü íà ïðàêòèêå ââèäó ìàëîãî r, äëÿ êîòîðîãî äîñòèãàåòñÿ ñóáëèíåéíîå âðåìÿ çàïðîñà è óìåðåííûå çàòðàòû ïàìÿòè. 2.2. Ìíîãîòàáëè÷íûå èíäåêñíûå ñòðóêòóðû äëÿ òî÷íîãî ïîèñêà ñ ãàðàí- òèÿìè ñðåäíåãî ñëó÷àÿ. Ðàññìîòðèì áîëåå ïðàêòè÷íûå ðåøåíèÿ äëÿ òî÷íîãî ñóáëèíåéíîãî ïîèñêà ïî dist Ham ñ ãàðàíòèÿìè ñðåäíåãî ñëó÷àÿ (Las Vegas). Ïðèâåäåííûå â ïîäðàçä. 2.2 ÈÑ îòíîñÿòñÿ ê êëàññó ìóëüòèèíäåêñíîãî õýøèðîâà- íèÿ. Èäåÿ ñîñòîèò â ðàçáèåíèè âåêòîðîâ íà íåñêîëüêî íåïåðåñåêàþùèõñÿ ÷àñòåé; äëÿ êàæäîé ÷àñòè âåêòîðà ñòðîèòñÿ ÷àñòè÷íàÿ ÈÑ (îáû÷íî òàáëè÷íàÿ), ñîäåðæàùàÿ âñå âåê- òîðû áàçû è ïîçâîëÿþùàÿ ïðîâîäèòü ýôôåêòèâíûé ïîèñê ïî ÷àñòè âåêòîðà. Ïðè âûïîë- íåíèè çàïðîñà èç êàæäîé ÈÑ èçâëåêàþò âåêòîðû áàçû, ÷àñòè êîòîðûõ ñîâïàäàþò èëè íàõîäÿòñÿ â ïðåäåëàõ íåêîòîðîãî dist Ham îò ñîîòâåòñòâóþùåé ÷àñòè âåêòîðà-çàïðîñà. Ýòè êàíäèäàòû óòî÷íÿþòñÿ íà âòîðîì ýòàïå ñòðàòåãèè F&R. Â ïîäðàçä. 2.2.1 ðàññìîòðå- íû ÈÑ ïîèñêà ñ ôèêñèðîâàííûì ðàäèóñîì çàïðîñà, à â ïîäðàçä 2.2.2 — ñ èçìåíÿåìûì. Äëÿ ÈÑ ñ ôèêñèðîâàííûì r íåîáõîäèìà îòäåëüíàÿ ÈÑ äëÿ êàæäîãî r. 2.2.1. Èíäåêñíûå ñòðóêòóðû ñ ôèêñèðîâàííûì ðàäèóñîì çàïðîñà. Â [45] âåê- òîðû ðàçáèâàþò íà M r� �1 ÷àñòåé. Òàêîå ðàçáèåíèå ãàðàíòèðóåò ñîâïàäåíèå ñ ÷àñ- òüþ âåêòîðà-çàïðîñà ïî êðàéíåé ìåðå îäíîé ÷àñòè èñêîìûõ âåêòîðîâ áàçû (ñì. òàêæå [46]). Ïðè ðàâíîìåðíîì ðàñïðåäåëåíèè äàííûõ è ðàçìåðíîñòè ÷àñòè d D M� / ñðåä- íåå êîëè÷åñòâî âåêòîðîâ áàçû â êîðçèíå N Nd D M/ / /2 2� � N D r/ /( )2 1� , ÷òî î÷åíü âåëèêî äëÿ áîëüøèõ r. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà êàíäèäàòîâ â [45] ïðåäëàãàþò ðàçáèâàòü âåêòîð íà áîëüøåå êîëè÷åñòâî M r� �1 ÷àñòåé, íî îáúåäè- íÿòü ýòè ÷àñòè. Òîãäà íå ìåíåå M r� ìàëûõ (äî îáúåäèíåíèÿ) ÷àñòåé âåêòîðîâ, ñîîòâåòñòâóþùèõ çàïðîñó rNN, ñîâïàäóò ñ ñîîòâåòñòâóþùèìè ÷àñòÿìè âåêòî- ðà-çàïðîñà. Êîëè÷åñòâî ðàçëè÷íûõ êîìáèíàöèé M r� ìàëûõ ÷àñòåé áåç ó÷åòà ïî- ðÿäêà èõ ñëåäîâàíèÿ ñîñòàâëÿåò L C C M M r M r� �� . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 173 Åñëè ïîñòðîèòü L ñîîòâåòñòâóþùèõ ÷àñòè÷íûõ ÈÑ, èçâëå÷åííûå èç íèõ (ïî îáúåäèíåííûì ÷àñòÿì) êàíäèäàòû áóäóò ãàðàíòèðîâàííî âêëþ÷àòü âñå âåêòîðû áàçû, ÿâëÿþùèåñÿ îòâåòîì íà çàïðîñ rNN. Ñðåäíåå êîëè÷åñòâî êàíäèäàòîâ â ÷àñ- òè÷íîé ÈÑ óìåíüøàåòñÿ äî N d M r/ ( )2 � , îäíàêî êîëè÷åñòâî ÈÑ âîçðàñòàåò ñ M äî L, óâåëè÷èâàÿ çàòðàòû ïàìÿòè. Êîìïðîìèññ èññëåäîâàí â [47]. Â ÈÑ MH [47] M r� ìàëûõ ÷àñòåé ðàñïîëàãàþò â íà÷àëå âåêòîðà, îñòàëüíûå ÷àñòè — â åñòåñòâåííîì ïîðÿäêå. Â êàæäîé èç L ÷àñòè÷íûõ ÈÑ âåêòîðû áàçû ñî- ðòèðóþò â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå, ÷òîáû áûñòðûì ïîèñêîì äèõîòîìèåé íàõîäèòü ñîâïàäàþùèå ñ çàïðîñîì îáúåäèíåííûå ÷àñòè. Íåäîñòàòêè ýòîé ÈÑ — áîëüøèå çàòðàòû ïàìÿòè O LND( ), ìàëûå çíà÷åíèÿ r (íà ïðàêòèêå r � 2 7, ,� ïðè D � 64). Åñëè íå òðåáîâàòü ïîëíîãî ñîâïàäåíèÿ ÷àñòåé âåêòîðîâ, êîëè÷åñòâî ÷àñòè÷- íûõ ÈÑ ìîæíî óìåíüøèòü: ïðè M r( ) /1 2 1� �� íå ìåíåå ÷åì äëÿ îäíîé ÷àñòè âåêòîðîâ dist Ham � 1 [48], à ïðè M r r rp p( ) / ( )� � �� 1 1 íå ìåíåå ÷åì äëÿ îäíîé ÷àñòè âåêòîðîâ dist Ham � rp [49]. Êàíäèäàòîâ â ÷àñòè÷íîé ÈÑ â ïðåäåëàõ ðàäèóñà rp íàõîäÿò ìîäèôèêàöèåé ÷àñòè âåêòîðà-çàïðîñà è ïîèñêîì ñîâïàäåíèé. Êîëè÷åñò- âî çàïðîñîâ óâåëè÷èâàåòñÿ ñ ðîñòîì rp , íàïðèìåð, ñ r �1 äëÿ rp � 0 äî M M D M� �( / ) � �r D/ 2 1� � äëÿ rp �1. Îäíàêî óìåíüøåíèå M ñ ðîñòîì rp ïðè- âîäèò ê óìåíüøåíèþ êîëè÷åñòâà ÷àñòè÷íûõ ÈÑ (è çàòðàò ïàìÿòè), êîëè÷åñòâà êàíäèäàòîâ â êàæäîé êîðçèíå, à òàêæå îáùåãî êîëè÷åñòâà êàíäèäàòîâ âî âñåõ èç- âëå÷åííûõ êîðçèíàõ [49]. Â ÈÑ HEngine [48] (âàðèàíò äëÿ ôèêñèðîâàííîãî r) ðàññìàòðèâàþò ðàçáèå- íèå íà M r� �� / 2 1 ÷àñòåé, ïðè ýòîì dist Ham � 1 äëÿ íå ìåíåå M r�� / 2 ÷àñòåé. Àíàëîãè÷íî [47] ñóùåñòâóåò L C M M r� � � �/2 ñïîñîáîâ ðàñïîëîæèòü M r�� / 2 ðàç- ëè÷íûõ ÷àñòåé ïåðâûìè. Ôîðìèðóþò L òàáëèö, â êîòîðûõ âåêòîðû óïîðÿäî÷èâà- þò ëåêñèêîãðàôè÷åñêè. Â îòëè÷èå îò [47] â L òàáëèöàõ íàõîäÿò íå òîëüêî âåêòî- ðû áàçû ñ ïîëíûì ñîâïàäåíèåì M r�� / 2 ÷àñòåé, íî è ñ dist Ham �1. Â HEngine êîëè÷åñòâî òàáëèö óìåíüøåíî â íåñêîëüêî ðàç ïî ñðàâíåíèþ ñ [47] ïðè íåêîòî- ðîì óìåíüøåíèè âðåìåíè çàïðîñà äëÿ r � 10. Â ÈÑ HmSearch [50] èñïîëüçóþò ðàçáèåíèå íà M ÷àñòåé, â ÷àñòè÷íîé ÈÑ äëÿ êàæäîé ÷àñòè ïðèìåíÿþò ïîèñê ñ dist Ham � 1. Äîïîëíèòåëüíûå óñëîâèÿ ôè- ëüòðàöèè ïîçâîëÿþò óâåëè÷èòü ïðàêòè÷åñêè äîñòèæèìûå D è r. Äëÿ áîëåå ðàâíî- ìåðíîãî ðàñïðåäåëåíèÿ âåêòîðîâ ïî êîðçèíàì (ïîäðàçä. 2.2.2) èñïîëüçóþò æàä- íîå ôîðìèðîâàíèå ðàçáèåíèé äëÿ ìèíèìèçàöèè ìàêñèìàëüíîé ÷àñòîòû âñòðå÷àå- ìîñòè ëþáîãî ïîäâåêòîðà áàçû. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà êàíäèäàòîâ HEngine â [49] ïðèìåíÿþò ðàçáèåíèÿ îáúåêòîâ íà ïîäìíîæåñòâà íà îñíîâå ðàññòîÿíèé äî îïîðíûõ îáúåêòîâ è íåðàâå- íñòâî òðåóãîëüíèêà (òàêèå ïîäõîäû ïðèâåäåíû â [4]). Êðîìå òîãî, çà ñ÷åò èñïîëüçî- âàíèÿ êîìïàêòíûõ ñòðóêòóð äàííûõ è äðóãèõ îïòèìèçàöèé ãàðàíòèðóåòñÿ óìåíüøå- íèå ïàìÿòè îò 18 äî 40 % ïðè ñîõðàíåíèè âðåìåíè çàïðîñà è äàæå óñêîðåíèå ïîèñêà ïðè r � { }2 3 4, , . Îáùåå âðåìÿ çàïðîñà ñîêðàùàåòñÿ â òðè-÷åòûðå ðàçà. 2.2.2. Èíäåêñíûå ñòðóêòóðû ñ ïåðåìåííûì ðàäèóñîì çàïðîñà. Â ÈÑ HEngine [48] (âàðèàíò äëÿ èçìåíÿåìîãî r) ïðè ïîñòðîåíèè âåêòîðû áàçû ðåêóð- ñèâíî äåëÿò íà äâå ÷àñòè, ïîêà èõ ðàçìåðíîñòè íå äîñòèãíóò çàäàííîãî ïîðîãîâî- ãî çíà÷åíèÿ. Âåêòîðû áàçû ñîðòèðóþò â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå â òàáëèöå äëÿ êàæäîé ÷àñòè. Ïðè ïîèñêå ó÷èòûâàþò, ÷òî äëÿ âåêòîðîâ ñ dist Ham � r ïðè ðàçáèåíèè íà äâå ÷àñòè dist Ham � � �r / 2 äëÿ îäíîé èëè äðóãîé ÷àñòè. Ïðè âûïîë- íåíèè çàïðîñà, åñëè r ïðåâûøàåò ïîðîã, âåêòîð-çàïðîñ äåëÿò íà äâå ÷àñòè, âäâîå óìåíüøàþò r è ðåêóðñèâíî ðåøàþò ïîëó÷èâøèåñÿ çàäà÷è. Îäíà èç ÷àñòåé âåêòî- ðà áàçû, êîòîðûé ÿâëÿåòñÿ îòâåòîì íà çàïðîñ, ïðè òàêîì ðåêóðñèâíîì ðàçáèåíèè äîëæíà ñîâïàñòü ñ ñîîòâåòñòâóþùåé ÷àñòüþ âåêòîðà-çàïðîñà. Åñëè äîñòèãíóòî ïîðîãîâîå çíà÷åíèå ðàçìåðíîñòè ÷àñòåé âåêòîðà, âûïîëíÿåòñÿ ëèíåéíûé ïîèñê 174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 ïî òåêóùèì òàáëèöàì. Îòíîñèòåëüíî ëèíåéíîãî ïîèñêà äîñòèãàåòñÿ óñêîðåíèå âûïîëíåíèÿ çàïðîñà äî 46 ðàç (D � 64, r � 2, ... , 7) ïðè óâåëè÷åíèè çàòðàò ïàìÿòè â 1.7 ðàç. Â ÈÑ Multi-index hashing (MIH) [51] ñòðîÿò òàáëèöó äëÿ êàæäîé èç M ÷àñ- òåé, ïðè ýòîì äëÿ çàïðîñà rNN íå ìåíåå ÷åì â îäíîé ÷àñòè dist Ham � �r r Mp � �/ . Ïîýòîìó ïðè âûïîëíåíèè çàïðîñà â êàæäîé èç M òàáëèö ìîäèôèêàöèåé ñîîòâå- òñòâóþùåé ÷àñòè âåêòîðà-çàïðîñà íàõîäÿò â êà÷åñòâå êàíäèäàòîâ âåêòîðû áàçû ñ ðàññòîÿíèåì dist Ham � � �r M/ îò ñîîòâåòñòâóþùåé ÷àñòè âåêòîðà-çàïðîñà. Èñïîëüçóþò log N êîìïîíåíòîâ â ÷àñòè âåêòîðà. Ïîêàçàíà ðàáîòà ÈÑ ïðè D äî 256; â îòëè÷èå îò ðàññìîòðåííûõ ðàíåå àëãîðèòìîâ r ñîñòàâëÿåò çíà÷èòåëü- íóþ äîëþ D . Ðåàëèçîâàíî òàêæå âûïîëíåíèå çàïðîñà kNN óâåëè÷åíèåì ðàäèóñà çàïðîñà rNN. Ïðè ñëó÷àéíîì âûáîðå êîìïîíåíòîâ ÷àñòåé êîððåëÿöèÿ ìåæäó íèìè (äëÿ ðåàëüíûõ áàç ñ íåðàâíîìåðíûì ðàñïðåäåëåíèåì äàííûõ) ìîæåò ïðèâîäèòü ê íå- ðàâíîìåðíîìó ðàñïðåäåëåíèþ âåêòîðîâ áàçû ïî êîðçèíàì òàáëèö. Ýòî óâåëè÷è- âàåò êîëè÷åñòâî êàíäèäàòîâ è çàìåäëÿåò âûïîëíåíèå çàïðîñà (íàïðèìåð, åñëè íå- êîòîðàÿ ÷àñòü âåêòîðîâ îäèíàêîâà ó âñåõ âåêòîðîâ áàçû è ó âåêòîðà-çàïðîñà, ïîèñê âûðîæäàåòñÿ â ëèíåéíûé). Äåêîððåëÿöèÿ êîìïîíåíòîâ â ÷àñòÿõ íà îñíîâå àíàëèçà áàçû ïðèâîäèò ê 20–50 % óñêîðåíèþ ïîèñêà [52, 51]. Â [53] â öåëÿõ ëó÷øåé áàëàíñèðîâêè êîð- çèí äëÿ êàæäîé ÷àñòè âåêòîðà ãåíåðèðóþò íîâûé õýø ñ èñïîëüçîâàíèåì ïðîåöè- ðîâàíèÿ íà ãëàâíóþ îñü âåêòîðîâ ýòîé ÷àñòè. Â [54] êîìïîíåíòû âåêòîðà âçâåøè- âàþò òàêèì îáðàçîì, ÷òî êîìïîíåíòû ñ áîëåå áëèçêîé ê 0.5 ÷àñòîòå 1 (èëè 0) ïî- ëó÷àþò áîëüøèé âåñ, è ðàçáèâàþò âåêòîðû íà ÷àñòè (ïðè÷åì íåîäèíàêîâîé ðàçìåðíîñòè) òàê, ÷òî â êàæäîé ÷àñòè ñóììàðíûé âåñ îäèíàêîâ. Â [55] ðàçáèåíèå ïðîâîäÿò ðåøåíèåì îïòèìèçàöèîííîé çàäà÷è, ìèíèìèçèðóþùåé ñóììó êâàäðà- òîâ ðàçíîñòè ýíòðîïèé âåêòîðîâ êàæäîé ÷àñòè è åå ñðåäíåãî çíà÷åíèÿ. Â [56] äëÿ óñêîðåíèÿ ïîèñêà çà ñ÷åò ñîêðàùåíèÿ êîëè÷åñòâà êàíäèäàòîâ ïðåäëàãàþò èñïîëüçîâàòü ÷àñòè ðàçëè÷íîé ðàçìåðíîñòè, ïðè âûáîðå êîòîðûõ íå ó÷èòûâàþòñÿ îñîáåííîñòè áàçû, ðàññìàòðèâàåòñÿ òàêæå ïðèáëèæåííûé ïîèñê. Â ðàáîòå [53] äëÿ ïîâûøåíèÿ êà÷åñòâà ðàíæèðîâàíèÿ êàíäèäàòîâ èñïîëüçó- þò âçâåøèâàíèå êîìïîíåíòîâ âåêòîðà. Â [55] óäàåòñÿ èçáåæàòü ýòàïà óòî÷íåíèÿ êàíäèäàòîâ ñòðàòåãèåé F&R. Äëÿ êàæäîé ÷àñòè èçâåñòíû êîðçèíû (è âåêòîðû â íèõ) äëÿ âñåõ çíà÷åíèé dist Ham � rp äî ñîîòâåòñòâóþùåé ÷àñòè âåêòîðà-çàïðî- ñà. Âñå ðàäèóñû çàïðîñîâ îò 0 äî r ìîæíî ïðåäñòàâèòü â âèäå ñóììû ïîäõîäÿùèõ ðàäèóñîâ äëÿ êàæäîé ÷àñòè. Äëÿ êàæäîé òàêîé êîìáèíàöèè ðàäèóñîâ ïåðåñå÷å- íèå ìíîæåñòâ êàíäèäàòîâ, ïîëó÷åííûõ äëÿ êàæäîé ÷àñòè, äàåò ìíîæåñòâî âåêòî- ðîâ, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà çàïðîñ. Âñå ýòè ìíîæåñòâà âåêòîðîâ îáúåäèíÿ- þò â îêîí÷àòåëüíûé îòâåò. Äëÿ ìàëûõ r ýòîò ìåòîä ðàáîòàåò áûñòðåå MIH è ÍmSearch. Ðàçíîâèäíîñòü MIH ïðèìåíÿåòñÿ â [57] äëÿ òî÷íîãî ïîèñêà kNN ïî sim cos ìåæäó áèíàðíûìè âåêòîðàìè ñ èñïîëüçîâàíèåì ñîîòíîøåíèé ìåæäó sim cos è dist Ham . 3. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÍÀ ÎÑÍÎÂÅ ËÎÊÀËÜÍÎ-×ÓÂÑÒÂÈÒÅËÜÍÎÃÎ ÕÝØÈÐÎÂÀÍÈß Â îòëè÷èå îò îáû÷íîãî õýøèðîâàíèÿ â ëîêàëüíî-÷óâñòâèòåëüíîì (locali- ty-sensitive hashing, LSH) LSH-ôóíêöèè ãåíåðèðóþò õýø-çíà÷åíèÿ òàê, ÷òî âå- ðîÿòíîñòü èõ ñîâïàäåíèÿ ó ñõîäíûõ îáúåêòîâ âûøå, ÷åì ó íåñõîäíûõ (ñì. îá- çîðû â [58, 59, 17, 31]). Èíäåêñíûå ñòðóêòóðû íà îñíîâå LSH — îäíè èç íå- ìíîãèõ ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè â õóäøåì ñëó÷àå äëÿ íåêîòîðûõ òèïîâ çàïðîñîâ ïðèáëèæåííîãî âåðîÿòíîñòíîãî ïîèñêà ïî ñõîäñòâó, êîòîðûå ðåàëèçîâàíû íà ïðàêòèêå. Áîëüøèíñòâî LSH-ôóíêöèé ðàçðàáîòàíî äëÿ îïðåäå- ëåííûõ ìåð ðàññòîÿíèÿ/ñõîäñòâà âåùåñòâåííûõ âåêòîðîâ è ìîãóò ïðèìåíÿòüñÿ äëÿ òàêèõ æå ìåð áèíàðíûõ âåêòîðîâ, êàê äëÿ ÷àñòíîãî ñëó÷àÿ. Ðÿä LSH-ôóíêöèé ïðåäíàçíà÷åí íåïîñðåäñòâåííî äëÿ ðàçëè÷íûõ ìåð ñõîäñòâà áè- íàðíûõ âåêòîðîâ, âêëþ÷àÿ ðàçðåæåííûå áîëüøîé ðàçìåðíîñòè. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 175 3.1. LSH-ôóíêöèè. Ñåìåéñòâî F õýø-ôóíêöèé h ÿâëÿåòñÿ ( , , , )r r p p1 2 1 2 -÷óâ- ñòâèòåëüíûì äëÿ ëþáûõ îáúåêòîâ a b, ïðè âûïîëíåíèè óñëîâèé [58, 59]: åñëè 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, ãäå âåðîÿòíîñòü Pr ñîîòâåòñòâóåò ñëó÷àéíîìó ðàâíîìåðíîìó âûáîðó õýø-ôóíêöèé h èç ñåìåéñòâà. Äëÿ ïîëåçíîãî LSH-ñåìåéñòâà r r1 2� è p p1 2� . Ýòî îïðåäåëåíèå LSH äàíî íà îñíîâå çàçîðà ðàññòîÿíèé ìåæäó ñõîäíûìè è íåñõîäíûìè îáúåêòàìè, àíàëîãè÷íîå îïðåäåëåíèå LSH ñóùåñòâóåò [60] íà îñíîâå çàçîðà ñõîäñòâ. Â äðóãîì îïðåäåëåíèè LSH íà îñíîâå ìîíîòîííîñòè âåëè÷èíû ñõîäñòâà [61] äëÿ LSH-ôóíêöèé äîëæíî âûïîëíÿòüñÿ Pr ( ) ( ) ( , )F h a h b a b{ } sim� � , ãäå sim — ìåðà ñõîäñòâà îáúåêòîâ, ïðèíèìàþùàÿ çíà÷åíèÿ â [0,1]. Îòìåòèì, ÷òî sim ìîæåò òàêæå ÿâëÿòüñÿ ìîíîòîííî âîçðàñòàþùåé ôóíêöèåé ñî çíà÷åíèÿìè â [0,1] îò íå- êîòîðîé äðóãîé ôóíêöèè ñõîäñòâà [62]. Àíàëîãè÷íîå îïðåäåëåíèå ñóùåñòâóåò è äëÿ ðàññòîÿíèé. Èç îïðåäåëåíèÿ LSH íà îñíîâå ìîíîòîííîñòè ñëåäóåò îïðåäå- ëåíèå íà îñíîâå çàçîðà [62]. Ïðîñòûì ïðèìåðîì LSH-ôóíêöèè äëÿ dist Ham ÿâëÿåòñÿ ôóíêöèÿ h, êîòîðàÿ ñëó÷àéíî âûáèðàåò îäèí èç êîìïîíåíòîâ âåêòîðà a : h ai( )a � [59], ò.å. âûïîëíÿåò ñýìïëèðîâàíèå ñ çàìåùåíèåì [17, 20]. Äëÿ ýòîé LSH-ôóíêöèè Pr {h h( ) ( )}a b� � � � � �Pr { dist Hama b Di i } ( , ) /1 a b . 3.2. Çàïðîñû ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó. Ïðèâåäåì òèïû çàïðîñîâ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó, êîòîðûå âûïîëíÿþò ðàçëè÷íûå ÈÑ LSH. Îáîçíà÷èì ( )c -rNN1 çàïðîñ ñ-ïðèáëèæåííîãî r-áëèæíåãî ñîñåäà (ñ-appro- ximate r-near neighbor); îí âîçâðàùàåò ëþáîé îáúåêò áàçû ñ ðàññòîÿíèåì, íå ïðå- âûøàþùèì cr ( c �1), îò îáúåêòà-çàïðîñà, åñëè ñóùåñòâóåò îáúåêò áàçû ñ ðàññòîÿ- íèåì, íå áîëüøèì r, îò îáúåêòà-çàïðîñà. Îáîçíà÷èì ( , )c � -rNN1 çàïðîñ âåðîÿòíîñòíîãî ñ-ïðèáëèæåííîãî r-áëèæíåãî ñîñåäà (randomized ñ-approximate r-near neighbor); îí ñ âåðîÿòíîñòüþ, íå ìåíüøåé 1� �, âîçâðàùàåò ëþáîé îáúåêò áàçû ñ ðàññòîÿíèåì, íå ïðåâûøàþùèì cr, îò îáú- åêòà-çàïðîñà, åñëè ñóùåñòâóåò îáúåêò áàçû ñ ðàññòîÿíèåì, íå áîëüøèì r, îò îáú- åêòà-çàïðîñà. Åñëè òàêîãî îáúåêòà íå ñóùåñòâóåò, òî ñëåäóåò îòâåò none èëè âîç- âðàùàåòñÿ îáúåêò ñ ðàññòîÿíèåì, íå ïðåâûøàþùèì cr. Îáîçíà÷èì ( )� -rNN çàïðîñ âñåõ âåðîÿòíîñòíûõ r-áëèæíèõ ñîñåäåé (all randomized r-near neighbors) èëè âåðîÿòíîñòíûé äèàïàçîííûé çàïðîñ; îí âîç- âðàùàåò âñå îáúåêòû áàçû ñ ðàññòîÿíèåì, íå áîëüøèì r, îò îáúåêòà-çàïðîñà è ñ âåðîÿòíîñòüþ, íå ìåíüøåé 1� �, äëÿ êàæäîãî òàêîãî îáúåêòà. Ðåäóêöèÿ çàïðîñîâ ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà ðàçëè÷íîãî òèïà ê çàïðîñàì áëèæíåãî ñîñåäà ðàññìîòðåíà â [30, 59, 31] (ñì. òàêæå ïîäðàçä. 1.2). Îäíàêî ýòà ðåäóêöèÿ òðåáóåò ïîñòðîåíèÿ îòäåëüíûõ ÈÑ äëÿ ìíîãèõ r, ÷òî çíà÷è- òåëüíî óâåëè÷èâàåò çàòðàòû ïàìÿòè è ïîýòîìó íå ïðèìåíÿåòñÿ íà ïðàêòèêå. Äëÿ âûïîëíåíèÿ çàïðîñîâ ïðèáëèæåííîãî NN ÷àñòî èñïîëüçóþò ÈÑ áåç ñïåöèôèöè- ðîâàííûõ ãàðàíòèé (êà÷åñòâî ïîèñêà ïðîâåðÿþò íà áàçàõ). Îòìåòèì, ÷òî îáîçíà÷åíèå NN â çàïðîñàõ ( )c -rNN1, ( , )c � -rNN1, ( )� -rNN èñ- ïîëüçóåòñÿ äëÿ áëèæíåãî ñîñåäà, à â çàïðîñàõ NN, kNN — äëÿ áëèæàéøåãî ñîñåäà. 3.3. Áàçîâàÿ èíäåêñíàÿ ñòðóêòóðà 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 êîíñòðóèðóþò ñâîþ õýø-òàáëèöó. (Òàêèì îáðàçîì, â LSH ñýìïëèðîâàíèåì äëÿ dist Ham òàáëè- öàì ñîîòâåòñòâóþò ðàçëè÷íûå ÷àñòè âåêòîðîâ, êîòîðûå ìîãóò ïåðåñåêàòüñÿ îò- äåëüíûìè êîìïîíåíòàìè â îòëè÷èå îò ÈÑ, ðàññìîòðåííûõ â ðàçä. 2.) Êàæäûé îáúåêò áàçû y ïîìåùàþò â îäíó êîðçèíó êàæäîé èç L õýø-òàáëèö — êîðçèíó, êî- òîðàÿ ñîîòâåòñòâóåò åãî õýøó g y( ) äëÿ ýòîé òàáëèöû. Òàêèì îáðàçîì, îáúåêòû 176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 ñ îäèíàêîâûìè çíà÷åíèÿìè g ïîïàäàþò â îäíó êîðçèíó. Òàê êàê ïðè N m�� 2 áîëüøèíñòâî ÿ÷ååê òàáëèö ïóñòû, ê LSH-õýøàì äîïîëíèòåëüíî ïðèìåíÿþò îá- û÷íîå õýøèðîâàíèå. Äðóãèå îñîáåííîñòè ðåàëèçàöèè áàçîâîé ÈÑ LSH îïèñàíû â [63]. Äëÿ âûïîëíåíèÿ çàïðîñà â ÈÑ LSH èñïîëüçóþò ñòðàòåãèþ F&R. Õýøè îáúåê- òà-çàïðîñà ãåíåðèðóþò òåìè æå LSH-ôóíêöèÿìè, ÷òî ïðèìåíÿëèñü äëÿ êîíñòðóèðî- âàíèÿ ÈÑ. Îáúåêòû-êàíäèäàòû èçâëåêàþò èç êîðçèí, õýøè êîòîðûõ ñîâïàäàþò ñ õý- øàìè îáúåêòà-çàïðîñà (êîëëèçèÿ). Äëÿ âûïîëíåíèÿ çàïðîñà ( , )c � -rNN1 âûáèðàþò ôèêñèðîâàííîå ÷èñëî îáúåêòîâ èç ýòèõ êîðçèí, íàïðèìåð 3L, âêëþ÷àÿ äóáëèêàòû («Ñòðàòåãèÿ 1» [58]). Äëÿ çàïðîñà ( )� -rNN èñïîëüçóþò âñå îáúåêòû èç ýòèõ êîðçèí («Ñòðàòåãèÿ 2» [58]). Îêîí÷àòåëüíûé ðåçóëüòàò ïîëó÷àþò ëèíåéíûì ïîèñêîì â ñïèñêå êàíäèäàòîâ ïî ìåðå ñõîäñòâà/ðàññòîÿíèÿ çàïðîñà. Äëÿ ñòðàòåãèè 1 âûáèðàþò m N N pp� �log log / log //1 22 1 , L p m� � 1 [59]. Ðåçóëüòàò ïîèñêà ïîëó÷àþò ñ ïîñòîÿííîé âåðîÿòíîñòüþ 1� �. Óìåíüøèòü � äî ïðîèçâîëüíî ìàëîãî çíà÷åíèÿ ìîæíî ïðèìåíåíèåì íóæíîãî êîëè÷åñòâà (L-òàá- ëè÷íûõ) ÈÑ LSH. Èñïîëüçóÿ � � � �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 � � . Íàïðèìåð, LSH ñýìïëèðîâàíèåì äëÿ áèíàðíûõ âåêòîðîâ ïðè c �1èìååò � � 1/ c [58, 59]. Ýòî ïëîòíàÿ ãðàíèöà, òàê êàê íèæíÿÿ ãðàíèöà � � �1 1/ ( )c oD [64]. Ïîýòîìó äëÿ c � 2 ïîëó÷àåì � �1 2/ , ò.å. íàõîäèì r-áëèæíåãî ñîñåäà ñ àïïðîêñèìàöèåé 2 çà âðåìÿ O N( ). Îòìåòèì, ÷òî ëîãàðèôìè÷åñêîå âðåìÿ íå îáåñïå÷èâàåòñÿ. Ïðè ðàñ÷åòå ïàðàìåòðîâ äëÿ ñòðàòåãèè 2 (çàïðîñ ( )� -rNN) âûáèðàþò [63] L pm� �� log log( )� � 1 1 , à çíà÷åíèå m, ìèíèìèçèðóþùåå âðåìÿ çàïðîñà, îïðåäå- ëÿþò ýêñïåðèìåíòàëüíî äëÿ áàçû è çàïðîñîâ. Òàêæå L âûáèðàþò (ïîäðàçä. 3.6.1), èñõîäÿ èç èìåþùåéñÿ ïàìÿòè, à m pL� �� log ( ) / log/1 1 1� . 3.4. Ïðèìåðû LSH-ôóíêöèé äëÿ áèíàðíûõ âåêòîðîâ. 3.4.1. Ñõîäñòâî Æàêêàðà. Äëÿ sim Jac LSH-õýøèðîâàíèå MinHash íà îñíîâå ñëó÷àéíûõ ïåðåñòàíîâîê ïðåäëîæåíî â [65–67]. Öåëî÷èñëåííîå õýø-çíà÷åíèå MinHash åñòü ìèíèìàëüíûé íîìåð íåíóëåâîãî êîìïîíåíòà âåêòîðà, ïîëó÷åííîãî ñëó÷àéíîé ïåðåñòàíîâêîé èñõîäíîãî. Äëÿ ðàçëè÷íûõ ïåðåñòàíîâîê ïîëó÷àþò ðàç- ëè÷íûå çíà÷åíèÿ MinHash. Ïîêàçàíî, ÷òî Pr {min min )} sim Jach h( ) ( ( , )a b a b� � . Ïîýòîìó MinHash ÿâëÿåòñÿ LSH. Äëÿ ñíèæåíèÿ çàòðàò ïàìÿòè è âû÷èñëèòåëüíîé ñëîæíîñòè ïîëó÷åíèÿ ìíîæåñ- òâà õýø-çíà÷åíèé MinHash ïðåäëîæåíû ìîäèôèêàöèè (ñì. îáçîðû â [17, 68, 69] è ññûëêè ê íèì). Îäíî èç íàïðàâëåíèé — ñîêðàùåíèå êîëè÷åñòâà áèòîâ â õýø-çíà÷åíèè (âïëîòü äî îäíîãî) â ðåçóëüòàòå îòáðàñûâàíèÿ ñòàðøèõ áè- òîâ [70], ÷òî íåñêîëüêî óâåëè÷èâàåò äèñïåðñèþ îöåíêè ñõîäñòâà. Äðóãîå íàïðàâ- ëåíèå — óìåíüøåíèå âðåìåíè ôîðìèðîâàíèÿ ñêåò÷åé. Èñïîëüçîâàíèå îäíîé ïå- ðåñòàíîâêè (èëè åå ýìóëÿöèè) ñ ïîñëåäóþùèì ðàçáèåíèåì âåêòîðà íà ÷àñòè è èç- âëå÷åíèåì õýø-çíà÷åíèÿ èç êàæäîé ÷àñòè òðåáóåò ðåøåíèÿ ïðîáëåìû ïóñòûõ ÷àñòåé [71, 17]. Ðàçëè÷íûå âàðèàíòû çàèìñòâîâàíèÿ õýø-çíà÷åíèé èç ñîñåäíèõ êîðçèí [17] óâåëè÷èâàþò äèñïåðñèþ îöåíêè ñõîäñòâà. Âàðèàíò [71] ïðèáëèæàåò äèñïåðñèþ ê MinHàsh ñ ïîìîùüþ âûáîðà ÷àñòè, èç êîòîðîé çàèìñòâóþò õýø-çíà- ÷åíèå, ïîñðåäñòâîì 2-Universal Hashing ñ èñïîëüçîâàíèåì íîìåðîâ òåêóùåé êîð- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 177 çèíû è ïîïûòêè õýøèðîâàíèÿ. Ïðåäëîæåííûé â [69] ìåòîä ïîëó÷åíèÿ õýø-çíà- ÷åíèé áåç ïåðåñòàíîâêè è ðàçáèåíèÿ íà îñíîâå mixed tabulation hash function óìåíüøàåò äèñïåðñèþ îöåíêè ñõîäñòâà ïî ñðàâíåíèþ ñ îäíîé ïåðåñòàíîâêîé è äàæå ñ MinHash. Äëÿ ïîñòðîåíèÿ LSH-òàáëèö ñîçäàþò ñêåò÷ è èç íåãî îïðåäå- ëåííûì îáðàçîì ñýìïëèðóþò õýø-çíà÷åíèÿ. Â ðàáîòå [72] ïîêàçàíî, ÷òî MinHash ìîæåò èñïîëüçîâàòüñÿ è êàê LSH äëÿ sim cos è èìååò çíà÷åíèå � ìåíüøåå, ÷åì äëÿ LSH SimHash [61] (êîòîðîå ïðåäëî- æåíî äëÿ dist ang ìåæäó âåêòîðàìè è ìîæåò ïðèìåíÿòüñÿ äëÿ sim cos). Ýòî ñïðàâåä- ëèâî è äëÿ 1-áèòîâîãî âàðèàíòà MinHash. Ïîñëåäíèå óëó÷øåíèÿ äëÿ sim Jac ðàññìîòðåíû â ïîäðàçä. 3.6.3. 3.4.2. Ñêàëÿðíîå ïðîèçâåäåíèå. Äëÿ sim dot â îáùåì ñëó÷àå LSH íå ñóùåñ- òâóåò íè äëÿ áèíàðíûõ âåêòîðîâ, íè äëÿ âåùåñòâåííûõ [72, 73]. Àñèììåòðè÷íîå LSH äëÿ sim dot áèíàðíûõ âåêòîðîâ ïðåäëîæåíî â [62]. Ïåðåä ïðèìåíåíèåì MinHash âåêòîðû-çàïðîñû è âåêòîðû áàçû ïðåîáðàçóþò ïî-ðàçíîìó. Ïóñòü A — ìàêñèìàëüíîå êîëè÷åñòâî íåíóëåâûõ êîìïîíåíòîâ â âåêòîðàõ áàçû. Ê âåêòîðàì áàçû y äîáàâëÿþò A � \| \|y åäèíè÷íûõ êîìïîíåíòîâ è A � \| \|y íóëåâûõ; ê âåêòî- ðàì-çàïðîñàì x äîáàâëÿþò A íóëåâûõ êîìïîíåíòîâ, A � \| \|x åäèíè÷íûõ è \| \|x íó- ëåâûõ. Äëÿ ïîëó÷åííûõ ïðåäñòàâëåíèé ïîèñê ïî sim Jac äàåò òàêîé æå ðåçóëüòàò, êàê ïîèñê ïî sim dot èëè sim cos. Ðåçóëüòàòû ïîèñêà ëó÷øèå, ÷åì ïðè èñïîëüçîâà- íèè àñèììåòðè÷íûõ LSH-ôóíêöèé äëÿ âåùåñòâåííûõ âåêòîðîâ, îñîáåííî äëÿ ðàçðåæåííûõ âåêòîðîâ áîëüøîé ðàçìåðíîñòè. Òàêîå æå ïðåîáðàçîâàíèå ïîçâîëÿ- åò èñïîëüçîâàòü LSH äëÿ dist Ham ïðè ïîèñêå ïî sim dot [62, 74]. 3.5. Ïîèñê ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà. Äëÿ ïîèñêà áëèæàéøåãî ñîñåäà ðåäóêöèåé ê ïîèñêó áëèæíåãî (ñì. ïîäðàçä. 1.2 è 3.2) íåîáõîäèìî ïîñòðî- åíèå ÈÑ äëÿ ìíîãèõ ðàäèóñîâ çàïðîñà, ïðè÷åì êàæäàÿ ÈÑ LSH äîëæíà ñîñòîÿòü èç L òàáëèö, ÷òî òðåáóåò î÷åíü áîëüøèõ çàòðàò ïàìÿòè. Â ðàáîòå [63] áàçîâóþ ÈÑ LSÍ äëÿ çàïðîñà ( , )c � -rNN1 ýâðèñòè÷åñêè èñïîëü- çóþò äëÿ ïîèñêà ïðèáëèæåííîãî áëèæàéøåãî ñîñåäà, ïîëàãàÿ ðàññòîÿíèå äî íåãî èçâåñòíûì. Â [75] äëÿ LSH ñýìïëèðîâàíèåì áîëåå ðàâíîìåðíîå ðàñïðåäåëåíèå êîìïîíåíòîâ âåêòîðà ïî òàáëèöàì (çà ñ÷åò æàäíîãî âûáîðà ðåäêî âñòðå÷àþùèõ- ñÿ êîìïîíåíòîâ) ïîâûñèëî òî÷íîñòü ïîèñêà NN. Â ðàáîòå [61] ïðåäëîæåíî ãåíåðèðîâàòü L O N c� ( )/1 ñëó÷àéíûõ ïåðåñòàíî- âîê êîìïîíåíòîâ âåêòîðîâ áàçû, äëÿ êàæäîé ïåðåñòàíîâêè N âåêòîðîâ áàçû çàíî- ñÿò â ñâîþ òàáëèöó, óïîðÿäî÷èâ ëåêñèêîãðàôè÷åñêè. Ïðè ïîñòóïëåíèè âåêòî- ðà-çàïðîñà åãî ñîîòâåòñòâóþùèå ïåðåñòàíîâêè èñïîëüçóþòñÿ äëÿ ïîèñêà äèõîòî- ìèåé äâóõ áëèæàéøèõ âåêòîðîâ â êàæäîé èç L òàáëèö. Ýòè 2L âåêòîðîâ áàçû ÿâëÿþòñÿ êàíäèäàòàìè, ñ êîòîðûìè âû÷èñëÿåòñÿ dist Ham âåêòîðà-çàïðîñà äëÿ ïî- ëó÷åíèÿ ïðèáëèæåííîãî NN (ñ íåèçâåñòíûì ðàññòîÿíèåì) ñ ïîñòîÿííîé âåðîÿò- íîñòüþ. Âûáîð áîëüøåãî êîëè÷åñòâà áëèæàéøèõ ê çàïðîñó âåêòîðîâ â êàæäîé òàáëèöå (âìåñòî óâåëè÷åíèÿ êîëè÷åñòâà ÈÑ) íà ïðàêòèêå óìåíüøàåò âåðîÿòíîñòü false negative. Â EWH [76] íà ýòàïå âûïîëíåíèÿ çàïðîñà ãåíåðèðóþò ìîäèôèêàöèè õýøåé çàïðîñà (äî íåêîòîðîãî dist Ham � R àíàëîãè÷íî ìîäèôèêàöèè çàïðîñà â ïîä- ðàçä. 1.4.1) è èñïîëüçóþò â êà÷åñòâå íà÷àëüíûõ êàíäèäàòîâ âñå âåêòîðû èç ñîîò- âåòñòâóþùèõ êîðçèí. Èì ïðèñâàèâàþò ðåéòèíã i R i iB C�� 0 , ãäå Ci — êîëè÷åñòâî õýøåé, ñîîòâåòñòâóþùèõ êàíäèäàòó, ñ dist Ham � i îò õýøà âåêòîðà-çàïðîñà, Bi — âåñ (íàïðèìåð, B m i mLi � �( ) / ( )). Äëÿ óòî÷íåíèÿ îòáèðàþò êàíäèäàòîâ ñ ðåé- òèíãîì, ïðåâûøàþùèì ïîðîãîâûé. Ïàðàìåòðû îïðåäåëÿþò ðåøåíèåì îïòèìèçà- öèîííîé çàäà÷è äëÿ êîíêðåòíîé áàçû. Âñëåäñòâèå âçâåøèâàíèÿ êàíäèäàòîâ ðàç- ìåð èõ ñïèñêà â EWH ãîðàçäî ìåíüøèé, ÷åì â LSH ïðè òîì æå êà÷åñòâå. Â ýêñïå- ðèìåíòàõ ñ ðåàëüíûìè äàííûìè ïðè D, ðàâíîé äî 1024, ñ ðàññòîÿíèåì äî NN, ðàâíûì äî D / 4, ïðè òîì æå âðåìåíè çàïðîñà îøèáêà EWH äî 15 ðàç ìåíüøå LSH, à ïðè òîé æå òî÷íîñòè âðåìÿ çàïðîñà äî 10 ðàç ìåíüøå. 178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 3.6. Ðàçâèòèÿ ïîäõîäà LSH. 3.6.1. ×óâñòâèòåëüíîñòü ê âåêòîðàì áàçû è çàïðîñîâ. Äëÿ áàçîâîé ÈÑ LSH, íàñòðîåííîé íà âûïîëíåíèå çàïðîñà ( , )c � -rNN1, ðåàëüíûå âðåìåíà âûïîë- íåíèÿ çàïðîñîâ çàâèñÿò îò ðàñïðåäåëåíèÿ ðàññòîÿíèé îò êîíêðåòíîãî âåêòîðà-çà- ïðîñà äî âåêòîðîâ êîíêðåòíîé áàçû è ìîãóò çíà÷èòåëüíî îòëè÷àòüñÿ. Â [77, 78] ïðåäëàãàþò ìîäèôèêàöèè ÈÑ LSH, ïîçâîëÿþùèå â ïðîöåññå âûïîëíåíèÿ çàïðî- ñà ïîëó÷èòü âðåìÿ, êîòîðîå äàëà áû ÈÑ LSH c ïàðàìåòðàìè, îïòèìàëüíî âûáðàí- íûìè äëÿ êîíêðåòíûõ âåêòîðà-çàïðîñà è âåêòîðîâ áàçû (÷òî òðåáóåò çíàíèÿ êîí- êðåòíîãî ðàñïðåäåëåíèÿ ðàññòîÿíèé ìåæäó íèìè). Â ðàáîòå [78] ðàññìàòðèâàþò çàïðîñ ( )� -rNN. Äëÿ áàçîâîé ÈÑ LSH è «òðóä- íûõ» çàïðîñîâ ñðåäíåå êîëè÷åñòâî êàíäèäàòîâ ìîæåò ñîñòàâëÿòü äî O L( )occ . Äëÿ ðåøåíèÿ ýòîé ïðîáëåìû â ìíîãîóðîâíåâîì àäàïòèâíîì LSH [78] ñòðîÿò íàáîðû (óðîâíè) LSH-òàáëèö äëÿ ðàçëè÷íûõ ñî÷åòàíèé m è L (L óâåëè÷èâàåòñÿ îò m). Äëÿ âñåõ êîðçèí ïîìèìî ññûëîê íà èõ îáúåêòû õðàíÿò êîëè÷åñòâî îáúåêòîâ. Ïðè âû- ïîëíåíèè çàïðîñà äëÿ íàáîðîâ (óðîâíåé) â ïîðÿäêå âîçðàñòàíèÿ m îïðåäåëÿþò êîëè÷åñòâî êàíäèäàòîâ (ñóììèðîâàíèåì êîëè÷åñòâà îáúåêòîâ â êîðçèíàõ òàáëèö óðîâíÿ, àäðåñóåìûõ õýøàìè çàïðîñà) è ïðåêðàùàþò ïîèñê (ïî êðèòåðèþ îñòàíî- âà) íà íåêîòîðîì óðîâíå. Ïðè ýòîì ñðåäíåå êîëè÷åñòâî êàíäèäàòîâ � ( / )occ ( occ)N � âñåãäà ìåíüøå N , à âàðèàíò ÈÑ ñ ìîäèôèêàöèåé çàïðîñà ïðè- áëèæàåò åãî ê íèæíåé ãðàíèöå O N( )� �occ . Ïðè ìàëîé âíóòðåííåé ðàçìåðíîñòè ÷àñòè îáúåêòîâ áàçû, áëèçêèõ ê çàïðîñó, âåðõíèå ãðàíèöû íà ñðåäíåå âðåìÿ çàïðîñà ìîãóò áûòü óëó÷øåíû äî O N(log ) . Ïðàêòè÷åñêîé ðåàëèçàöèè ïîäõîäà ïðåïÿòñòâóþò áîëüøèå çàòðàòû ïàìÿòè. Â àëãîðèòìå [79], êîòîðûé ìîæåò ïðèìåíÿòüñÿ íà ïðàêòèêå, äëÿ çàïðîñà ( )� -rNN êîíñòðóèðóþò ÈÑ LSH äëÿ ôèêñèðîâàííîãî L, âûáèðàÿ m pL� �� log ( ) / log/1 1 1� (ñì. ïîäðàçä. 3.3, ñòðàòåãèÿ 2). ×òîáû ïðè âûïîëíåíèè êîíêðåòíîãî çàïðîñà âûáðàòü èñïîëüçîâàíèå áàçîâîé ÈÑ LSH ëèáî ëèíåéíîãî ïîèñêà, ïðåäëàãàåòñÿ áûñòðî îöåíèâàòü âðåìÿ çàïðîñà äëÿ LSH. Äëÿ ýòîãî â Hybrid LSH [79] ñ êàæäîé õýø-êîðçèíîé àññîöèèðîâàíà ñòðóêòóðà Hyperloglog [80], êîòîðàÿ ïîçâîëÿåò àïïðîêñèìèðîâàòü ÷èñëî îáúåêòîâ áåç äóáëèêàòîâ â âû- áðàííûõ õýøåì çàïðîñà L êîðçèíàõ. Îòìåòèì, ÷òî ïîäõîäû ýòîãî ïîäðàçäåëà ïðèìåíèìû òàêæå è ê âåùåñòâåí- íûì âåêòîðàì. 3.6.2. Òî÷íûé ïîèñê áèíàðíûõ âåêòîðîâ ïî ðàññòîÿíèþ Õýììèíãà. Èíäåêñíàÿ ñòðóêòóðà covering LSH (cLSH) [30 ] â îòëè÷èå îò áàçîâîé ÈÑ LSH ïî- çâîëÿåò âûïîëíÿòü çàïðîñû ïî dist Ham áåç âîçìîæíîñòè ïîòåðè íåêîòîðûõ îáúåê- òîâ-îòâåòîâ (ò.å. áåç false negatives). Âìåñòî ñëó÷àéíîãî íåçàâèñèìîãî âûáîðà êîìïîíåíòîâ g ñåìåéñòâî cLSH-ôóíêöèé êîíñòðóèðóþò òàê, ÷òî äëÿ ëþáîé ïàðû áèíàðíûõ âåêòîðîâ ñ dist Ham � r ñóùåñòâóåò ôóíêöèÿ ñåìåéñòâà, äëÿ êîòîðîé äîñòèãàåòñÿ êîëëèçèÿ èõ cLSH-õýøåé. Äëÿ cr N� log ïîëó÷àþò L Nr c� � ��2 1 21 1/ è � �1/ ñ, ò.å. îïòèìàëüíîå äëÿ áàçîâîãî LSH. Äëÿ ïðîèçâîëüíûõ r c, , N çíà÷åíèå � �1 38. / c. Ïðè âûïîëíåíèè çàïðîñà áëèæíåãî ñîñåäà âîçâðàùàþò ïåðâûé âåêòîð-êàíäèäàò y : dist Ham ( , )y x � cr. Åñëè îãðàíè÷èòü êîëè÷åñòâî êàíäèäàòîâ (ñòðàòåãèÿ 1), ïîëó- ÷èì îòâåò íà çàïðîñ ( , )c � -rNN1 çà ãàðàíòèðîâàííîå âðåìÿ DN o�� ( )1 , îäíàêî ñ âîçìîæíîñòüþ false negative. Â ïðîòèâíîì ñëó÷àå ïîëó÷èì ïîèñê áåç false negative ñî ñðåäíèì âðåìåíåì çàïðîñà ( )c -rNN1 ìåíåå DN o�� ( )1 (ðàíäîìèçàöèÿ Las Vegas). Äëÿ îïðåäåëåíèÿ ãðàíèö âðåìåíè ñ âûñîêîé âåðîÿòíîñòüþ ðàññìàò- ðèâàþò íàáîð èç O N(log ) ÈÑ ñLSH. Åñëè ïîèñê â ÈÑ ïðåâûñèë â äâà ðàçà ñðåä- íåå âðåìÿ, ïåðåõîäÿò ê ñëåäóþùåé ÈÑ, à åñëè âñå ÈÑ ïðîéäåíû, ïðèìåíÿþò ëè- íåéíûé ïîèñê, ÷òî ñëó÷àåòñÿ ñ ïîëèíîìèàëüíî ìàëîé âåðîÿòíîñòüþ îò N . Äëÿ çà- ïðîñà rNN èç êîðçèí ñ êîëëèçèÿìè èçâëåêàþò âñåõ êàíäèäàòîâ (ñòðàòåãèÿ 2). Òàê ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 179 êàê g èìåþò áîëüøóþ ðàçìåðíîñòü D, âàðèàíòàìè óíèâåðñàëüíîãî õýøèðîâàíèÿ èõ ïðåîáðàçóþò â õýø-çíà÷åíèÿ ïðèåìëåìîé ðàçìåðíîñòè O N(log ). Â áûñòðîì covering LSH (fcLSH) [81] ñëîæíîñòü ïîëó÷åíèÿ (èòîãîâûõ, ò.å. ïîñëå óíèâåðñàëüíîãî õýøèðîâàíèÿ) çíà÷åíèé fcLSH-ôóíêöèé óìåíüøàþò ñ O LD( ) äî O D L L( log )� ñ ïîìîùüþ èñïîëüçîâàíèÿ ìàòðèöû Àäàìàðà è áûñòðîãî ïðåîáðàçîâàíèÿ Àäàìàðà FHT. Äëÿ r, ðàâíîãî äî 20, íàáëþäàåòñÿ ïðåâîñõîäñòâî ïî âðåìåíè íàä LSH, cLSH, MIH [51]. Íåäîñòàòêîì cLSH è fcLSH ÿâëÿåòñÿ ýêñïîíåíöèàëüíàÿ çàâèñèìîñòü L îò r. 3.6.3. Ëîêàëüíî ÷óâñòâèòåëüíàÿ ôèëüòðàöèÿ. Ðàçáèåíèÿ ïðîñòðàíñòâà íà îáëàñòè ñ ïîìîùüþ LSH-ôóíêöèè âûïîëíÿþòñÿ áåç ïåðåêðûòèÿ. Êðîìå òîãî, îá- ëàñòè äîâîëüíî ìàëûå, ÷òî îãðàíè÷èâàåò êîëè÷åñòâî íåñõîäíûõ âåêòîðîâ â êîð- çèíå. Â [82] ïðåäëîæåíà àëüòåðíàòèâà LSH — ëîêàëüíî ÷óâñòâèòåëüíûå ôèëüòðû (Locality Sensitive Filters, LSF). Â îòëè÷èå îò LSH êàæäîìó ôèëüòðó LSF ñîîòâå- òñòâóåò îäíà ñëó÷àéíàÿ îáëàñòü ïðîñòðàíñòâà, îáëàñòè ðàçëè÷íûõ ôèëüòðîâ ìî- ãóò ïåðåêðûâàòüñÿ è èõ êîëè÷åñòâî ìîæåò áûòü î÷åíü áîëüøèì. Äëÿ îïðåäåëå- íèÿ, êàêèì îáëàñòÿì ïðèíàäëåæèò îáúåêò, çà âðåìÿ, ïðîïîðöèîíàëüíîå êîëè÷åñ- òâó òàêèõ îáëàñòåé, èñïîëüçóþò ñïåöèàëüíûå ñòðóêòóðû äàííûõ è íå âïîëíå ñëó÷àéíûå îáëàñòè, êîòîðûå, îäíàêî, îáåñïå÷èâàþò íóæíûå õàðàêòåðèñòèêè [82–84]. Èíäåêñíûå ñòðóêòóðû LSF ïîçâîëÿþò ãèáêèé êîìïðîìèññ ìåæäó çàòðà- òàìè ïàìÿòè è âðåìåíåì ïîèñêà (âêëþ÷àÿ ðåæèì LSH), à òàêæå ìåíüøèå çíà÷å- íèÿ � â ðåæèìå LSH äëÿ äàííûõ íåáîëüøîé ðàçìåðíîñòè D O N� (log ). Ïîäîáíî LSH â îáû÷íîì LSF íóëåâàÿ âåðîÿòíîñòü false negatives îáåñïå÷èâàåòñÿ òîëüêî ïðè êîëè÷åñòâå îáëàñòåé, ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè. Â [84] ïðåäëîæåíî îáîáùåíèå LSH, LSF è ÈÑ â êàòåãîðèþ Locality-Sensitive Maps. Ðàññìàòðèâàþò çàïðîñû ( , )c � -rNN1 ïî sim BB. Äëÿ âåêòîðîâ ñ îäèíàêîâîé õýììèíãîâîé íîðìîé ýòî ïîçâîëÿåò âûïîëíÿòü ïîèñê è ïî äðóãèì ìåðàì ðàññòîÿ- íèÿ/ñõîäñòâà äëÿ áèíàðíûõ âåêòîðîâ (ñì. ïîäðàçä. 1.1). Äëÿ òàêèõ ðàçðåæåííûõ âåêòîðîâ ïîëó÷åíî � ëó÷øåå, ÷åì äëÿ äðóãèõ LSH-ôóíêöèé (MinHash, ñýìïëèðó- þùèé LSH, ñôåðè÷åñêèé LSH), è äàæå ëó÷øåå, ÷åì äëÿ çàâèñèìîãî îò äàííûõ LSH (ïîäðàçä. 3.6.4) äëÿ çíà÷èòåëüíîé îáëàñòè çíà÷åíèé ñõîäñòâ. Íà îñíîâå LSF â [85] ïðåäëîæåí òåîðåòè÷åñêèé àëãîðèòì ïîèñêà ( )c -rNN1 ïî dist Ham áåç false negatives ñ � � �1 1/ ( )c o , ò.å. ëó÷øèì, ÷åì � �1 38. / c â [30]. Ïðè cr D� / 2 ïîëó÷åíî � � �1 2 1/ ( )c (ïîäðàçä. 3.6.4). Äëÿ sim BB è sim Jac äîñòèãàþò çíà÷åíèÿ � èç [84], íî áåç false negatives. 3.6.4. Çàâèñèìîå îò äàííûõ LSH. Äëÿ çàâèñèìîãî îò äàííûõ LSH (íî ñ ãà- ðàíòèÿìè õóäøåãî ñëó÷àÿ) äëÿ dist Ham â [86] ïîëó÷åíî îïòèìàëüíîå çíà÷åíèå � � � �1 2 1 1/ ( ) ( )c o , ò.å. ëó÷øåå, ÷åì � �1/ c äëÿ íåçàâèñèìîãî îò äàííûõ ñýìïëè- ðóþùåãî LSH. Îäíàêî çàâèñÿùàÿ îò äàííûõ LSH-ôóíêöèÿ âû÷èñëèòåëüíî ñëèø- êîì ñëîæíà äëÿ ïðàêòè÷åñêîãî ïðèìåíåíèÿ. Â [87] ïðîâåäåí àíàëèç ìîäèôèêà- öèè LSH Forest [88] (âìåñòî LSH-òàáëèö èñïîëüçóþòñÿ ïðåôèêñíûå äåðåâüÿ), ïîñòðîåííîãî íà ñëó÷àéíî ïåðåñòàâëåííûõ âåêòîðàõ áàçû. Õîòÿ ïîëó÷åííîå � õóæå îïòèìàëüíîãî � � �1 2 1/ ( )c , ýòîò àëãîðèòì ìîæåò ïðèìåíÿòüñÿ íà ïðàêòèêå è � ëó÷øå 1/ c. 4. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÍÀ ÎÑÍÎÂÅ ÄÅÐÅÂÜÅÂ Äëÿ ïîèñêà áèíàðíûõ âåêòîðîâ ïî ìåòðè÷åñêèì ðàññòîÿíèÿì, íàïðèìåð dist Ham , â ïðèíöèïå ïðèìåíèìû äðåâîâèäíûå ÈÑ ñ èåðàðõè÷åñêèìè ðàçáèåíè- ÿìè íà îáëàñòè, ðàçðàáîòàííûå äëÿ áîëåå îáùèõ ñëó÷àåâ ìåòðè÷åñêèõ è âåê- òîðíûõ ïðîñòðàíñòâ [21, 22, 23, 1]. Äðåâîâèäíûå ÈÑ äëÿ òî÷íîãî ïîèñêà ïî dist Ham (âêëþ÷àÿ íåáèíàðíûå ñòðîêè ñ ðàçëè÷íûìè àëôàâèòàìè äëÿ êîìïîíåíòîâ ñ ðàçëè÷íûìè ID) ïðåäëîæåíû â [89, 90]. Ê ÈÑ êëàññà ðàçáèåíèÿ äàííûõ (òèïà R-tree [22]) îòíîñèòñÿ ND-tree [89], à ê ÈÑ êëàññà ðàçáèåíèÿ ïðîñòðàíñòâà (òèïà KD-tree [22]) îòíîñèòñÿ NSP-tree [90]. Ïðåèìóùåñòâàìè äåðåâüåâ äëÿ òî÷íîãî ïîèñêà ÿâëÿþòñÿ: äåòåðìèíèðîâàííîñòü àë- ãîðèòìà, âîçìîæíîñòü âûïîëíåíèÿ çàïðîñîâ rNN ñ èçìåíÿåìûì ðàäèóñîì è çàïðî- 180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 ñîâ kNN. Ê èõ íåäîñòàòêàì îòíîñÿòñÿ: ýêñïîíåíöèàëüíàÿ çàâèñèìîñòü âðåìåíè ïî- èñêà îò D (â õóäøåì è äàæå â ñðåäíåì ñëó÷àå), îòñóòñòâèå ó÷åòà îñîáåííîñòåé áè- íàðíûõ âåêòîðîâ, à äëÿ ND-tree [89] è NSP-tree [90] — ýêñïåðèìåíòàëüíîå ñðàâíåíèå òîëüêî ñ ìåòðè÷åñêèìè äåðåâüÿìè [23, 1] è ëèíåéíûì ïîèñêîì. Øèðîêî ðàñïðîñòðàíåíî óñêîðåíèå ïîèñêà äðåâîâèäíûìè ÈÑ çà ñ÷åò ðàí- íåãî îñòàíîâà ïîèñêà [4], ÷òî äåëàåò åãî ïðèáëèæåííûì, áåç ñòðîãèõ ãàðàíòèé êà÷åñòâà ðåçóëüòàòîâ îòíîñèòåëüíî ëèíåéíîãî ïîèñêà. Â [75] â çàäà÷å ïîèñêà ïðèáëèæåííîãî NN äëÿ áèíàðíûõ âåêòîðîâ ïî dist Ham ýêñïåðèìåíòàëüíî èññëå- äîâàíû ÈÑ äëÿ âåùåñòâåííûõ âåêòîðîâ: ëåñ (ìíîæåñòâî) KD-trees [39], KM-tree [39] íà îñíîâå èåðàðõè÷åñêîé êëàñòåðèçàöèè K-means, VP-tree [4] (íåëèñòîâûå óçëû ñîîòâåòñòâóþò öåíòðàì êëàñòåðîâ, äàííûå íàõîäÿòñÿ â ëèñòîâûõ óçëàõ). Ïîëó÷åíû ïëîõèå ðåçóëüòàòû. Äëÿ ëåñà KD-trees èõ îáúÿñíÿþò [75] ÷óâñòâèòåëü- íîñòüþ ê øóìó â äàííûõ: ñìåíà îäíîãî áèòà ïðèâîäèò ê ïåðåõîäó íà äðóãîå ïîä- äåðåâî. Íàëè÷èå áîëüøîãî êîëè÷åñòâà âåêòîðîâ ñ îäèíàêîâûì dist Ham îò öåí- òðîâ îáëàñòåé Âîðîíîãî («òîëñòûå ãðàíèöû»), îñîáåííî ïðè ìàëûõ D , ïðèâîäèëî ê èõ ñëó÷àéíîìó íàçíà÷åíèþ îäíîé èëè äðóãîé îáëàñòè â èñïîëüçîâàííîé ðåàëèçàöèè KM-tree è VP-tree. Äëÿ óñòðàíåíèÿ ýòèõ íåäîñòàòêîâ â [39, 75] ïðèìåíÿþò ëåñ ðàíäîìèçèðîâàí- íûõ KM-trees, ìîäèôèöèðîâàííûõ çà ñ÷åò ñëó÷àéíîãî (áåç ïîâòîðåíèÿ) âûáîðà âåêòîðîâ áàçû â êà÷åñòâå öåíòðîâ êëàñòåðîâ. Â FLANN [39] äëÿ âñåõ äåðåâüåâ èñ- ïîëüçóþò îáùóþ ïðèîðèòåòíóþ î÷åðåäü, êóäà ïðè ñïóñêå èç êîðíåâîãî â ëèñòî- âîé óçåë (â ëèñòüÿõ õðàíÿòñÿ îáúåêòû áàçû), îáëàñòè êîòîðîãî ïðèíàäëåæèò âåê- òîð-çàïðîñ, çàíîñÿò óçëû ïðîìåæóòî÷íûõ óðîâíåé â ïîðÿäêå âîçðàñòàíèÿ ðàññòî- ÿíèé äî âåêòîðà-çàïðîñà. Ïî äîñòèæåíèè ëèñòà âñå åãî îáúåêòû ñðàâíèâàþò ñ âåêòîðîì-çàïðîñîì ëèíåéíûì ïîèñêîì ïî dist Ham . Ïîñëå îäíîêðàòíîãî ñïóñêà êîðåíü–ëèñò ïî âñåì äåðåâüÿì ïîèñê ïðîäîëæàþò, èçâëåêàÿ èç î÷åðåäè áëèæàé- øèé óçåë è îñóùåñòâëÿÿ îáõîä äåðåâà îò íåãî. Ïîèñê îñòàíàâëèâàþò ïî ïîñåùå- íèè çàäàííîãî êîëè÷åñòâà âåêòîðîâ áàçû. Â ëåñó Parc-trees [75] èñïîëüçóþò îäíî- êðàòíûé ñïóñê êîðåíü–ëèñò áåç äàëüíåéøåãî îáõîäà, êîëè÷åñòâî ïîñåùåííûõ âåêòîðîâ ðåãóëèðóþò êîýôôèöèåíòîì âåòâëåíèÿ K è êîëè÷åñòâîì äåðåâüåâ. Òà- êèå ÈÑ ïîçâîëÿþò âûïîëíÿòü çàïðîñ ïðèáëèæåííûõ kNN è íà ïðàêòèêå èñïîëü- çóþòñÿ ñ âåêòîðàìè ðàçìåðíîñòüþ äî ñîòåí áèòîâ (D � 256). Ïî ñðàâíåíèþ ñ ëè- íåéíûì ïîèñêîì âûïîëíåíèå çàïðîñà óñêîðÿåòñÿ â 10–100 ðàç äëÿ òî÷íîñòè â äè- àïàçîíå 50–99 %. Ýòî ìåíüøå, ÷åì óñêîðåíèå ïîäîáíûõ ÈÑ äëÿ âåùåñòâåííûõ âåêòîðîâ, òàê êàê ëèíåéíûé ïîèñê äëÿ áèíàðíûõ âåêòîðîâ î÷åíü áûñòðûé. Ñðàâ- íåíèå ñ LSH ïîêàçàëî ïðèìåðíî îäèíàêîâóþ èëè ëó÷øóþ ñêîðîñòü FLANN ïðè â íåñêîëüêî ðàç ìåíüøèõ çàòðàòàõ ïàìÿòè (íàïðèìåð, â øåñòü ðàç äëÿ òî÷íîñòè áîëüøåé 90 %). Òàêèì îáðàçîì, ïðè èñïîëüçîâàíèè ëåñà ïîëó÷àþò íåïëîõèå ðåçóëüòàòû äëÿ ïðèáëèæåííîãî ïîèñêà ïî dist Ham . Â ðàáîòå [91] öåíòðû êëàñòåðîâ âûáèðàþò íå ñëó÷àéíûå, à óäàëåííûå îò óæå îòîáðàííûõ áîëåå ÷åì íà ïîðîãîâîå ðàññòîÿíèå (äðóãèå ïîäîáíûå ýâðèñòèêè ñì. â [4]). Ðàññìàòðèâàåìûå ÈÑ ñòðîÿò ïî âåêòîðàì ñíèæåííîé ðàçìåðíîñòè, êî- òîðûå ïîëó÷àþò óïîðÿäî÷åíèåì êîìïîíåíòîâ ïî âåëè÷èíå äèñïåðñèè è îòáîðàì çàäàííîãî êîëè÷åñòâà. Ðåçóëüòàòû ïðåâûøàþò MIH è áèíàðíûé FLANN. Íàñòðîéêà öåíòðîâ êëàñòåðîâ ïîä äàííûå (íàïðèìåð, â KMedians êîìïîíåíòó ïðèñâàèâàþò òàêîå æå çíà÷åíèå, ÷òî è ó áîëüøèíñòâà âåêòîðîâ êëàñòåðà) ðàñ- ñìîòðåíà â [92–94]. Â ðàáîòå [95] ðåøàþò çàäà÷ó ïîèñêà ïî sim dot â áàçå ïëîòíûõ ñëó÷àéíî ñãåíå- ðèðîâàííûõ áèíàðíûõ âåêòîðîâ { }� �1 1, D áîëüøîé ðàçìåðíîñòè D, âåêòîð-çàïðîñ ÿâëÿåòñÿ ñëó÷àéíî èñêàæåííûì âåêòîðîì áàçû (ðàçä. 6). Ïîñëåäíþþ èåðàðõè÷åñêè ðàçáèâàþò íà íåïåðåñåêàþùèåñÿ ÷àñòè, äëÿ êàæäîé èç êîòîðûõ ñòðîÿò ïðîòîòèï ñóììèðîâàíèåì åå âåêòîðîâ, âçâåøåííûõ ñëó÷àéíûìè ÷èñëàìè èç { , }� �1 1 . Ïðîòî- òèïàì ñîîòâåòñòâóþò óçëû äåðåâà. Ïðè âûïîëíåíèè çàïðîñà íàõîäÿò sim dot âåêòî- ðà-çàïðîñà ñ âåêòîðàìè óçëîâ è ïåðåõîäÿò â óçåë ñ íàèáîëüøèì çíà÷åíèåì. Îñòàëüíûå çíà÷åíèÿ è èõ óçëû çàïîìèíàþò â ïðèîðèòåòíîé î÷åðåäè. Â ëèñòüÿõ çà- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 181 ïîìèíàþò çíà÷åíèÿ sim dot ñ ñîîòâåòñòâóþùèìè âåêòîðàìè áàçû. Ïîèñê îñòàíàâ- ëèâàþò ïî ïðåâûøåíèè sim dot ïîðîãîâîãî çíà÷åíèÿ, êîòîðîå îïðåäåëÿþò ñ ó÷åòîì âåëè÷èíû èñêàæåíèÿ âåêòîðà-çàïðîñà. Åñëè îíî íå ïðåâûøåíî â ëèñòå, èç ïðèîðè- òåòíîé î÷åðåäè èçâëåêàþò óçåë ñ íàèáîëüøèì çíà÷åíèåì. Äëÿ ïîâûøåíèÿ íàäåæ- íîñòè ïîèñê ïðîäîëæàþò è ïîñëå âûïîëíåíèÿ êðèòåðèÿ îñòàíîâà. Ïðè íàäëåæà- ùåì âûáîðå ïîðîãà âåðîÿòíîñòü ïîëó÷åíèÿ òî÷íîãî NN áëèçêà ê 1. Â [96] ÈÑ HA-index äëÿ ïîèñêà ñ èçìåíÿåìûì r ìîæíî ðàññìàòðèâàòü êàê èå- ðàðõè÷åñêèé ãðàô, ãäå ïðîìåæóòî÷íûå óçëû ïðåäñòàâëÿþò ïîäìíîæåñòâà êîìïî- íåíòîâ, íå ïåðåñåêàþùèåñÿ â ðàçëè÷íûõ ïóòÿõ îò âåðõíåãî óðîâíÿ ê íèæíåìó. Ïå- ðåä ïîñòðîåíèåì âåêòîðû óïîðÿäî÷èâàþò â ïîðÿäêå Ãðýÿ. Âåêòîðû áàçû õðàíÿòñÿ â ëèñòüÿõ è ïðåäñòàâëÿþò ñîáîé êîíêàòåíàöèþ ïîäìíîæåñòâ êîìïîíåíòîâ â ðàç- ëè÷íûõ ïóòÿõ îò óçëîâ âåðõíåãî óðîâíÿ â ëèñò. Ïðè ïîèñêå âûïîëíÿþò îáõîä ìå- òîäîì breadth-first, â î÷åðåäü çàíîñÿò íåïîñåùåííûå ïóòè, êîòîðûå óäîâëåòâîðÿþò óñëîâèÿì çàïðîñà. Óñêîðåíèÿ âûïîëíåíèÿ çàïðîñà äîñòèãàþò çà ñ÷åò óñòðàíåíèÿ èçáûòî÷íûõ è äóáëèðóþùèõñÿ âû÷èñëåíèé ðàññòîÿíèé. Ìåòîä çíà÷èòåëüíî ëó÷- øèé, ÷åì MH [47] è HEngine [48] äëÿ rNN, à òàêæå LSH è LSB-tree [97] äëÿ ïðè- áëèæåííîãî kNN, êàê ïî çàòðàòàì ïàìÿòè, òàê è ïî âðåìåíè çàïðîñà, ïîýòîìó àêòó- àëüíî åãî ñðàâíåíèå ñ äðóãèìè ÈÑ. Îòìåòèì, ÷òî âñå ðàññìîòðåííûå ÈÑ ïðèìåíÿëèñü äëÿ ïëîòíûõ áèíàðíûõ âåêòîðîâ. 5. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÍÀ ÎÑÍÎÂÅ ÃÐÀÔÎÂ ÑÎÑÅÄÑÒÂÀ Äëÿ ïðèáëèæåííîãî ïîèñêà áëèæàéøèõ ñîñåäåé â ìåòðè÷åñêèõ è íåìåòðè÷åñ- êèõ ïðîñòðàíñòâàõ óñïåøíî èñïîëüçóþò ãðàôû ñîñåäñòâà (îáúåêòû áàçû ïðåä- ñòàâëåíû óçëàìè, êàæäûé îáúåêò áàçû ñîåäèíåí ñ áëèæàéøèìè îáúåêòàìè) (ñì. îáçîð â [4]). Çàïðîñ âûïîëíÿþò ñòàðòîì ñ íåêîòîðîãî îáúåêòà áàçû è ïå- ðåõîäîì íà íåïîñåùåííûé îáúåêò-ñîñåä, áîëåå áëèçêèé ê îáúåêòó-çàïðîñó. Ïåðåõîäû âûïîëíÿþò, ïîêà ñóùåñòâóþò òàêèå îáúåêòû-ñîñåäè. Ïîñêîëüêó ëó÷øèé èç íàéäåííûõ îáúåêòîâ ìîæåò íå ÿâëÿòüñÿ áëèæàéøèì (èëè äàæå «õîðîøèì») ñîñåäîì, âûïîëíÿþòñÿ ðåñòàðòû ïîèñêà ñ äðóãèõ îáúåê- òîâ èëè ïåðåõîä íà íå ñàìûå áëèçêèå ê îáúåêòó-çàïðîñó îáúåêòû îêðåñòíîñòåé. Òî÷íûé ïîèñê òðåáóåò ïîñåùåíèÿ âñåõ îáúåêòîâ áàçû. Äëÿ îãðàíè÷åíèÿ âðåìåíè çàïðîñà ïîèñê îñòàíàâëèâàþò ïî äîñòèæåíèè çàäàííîãî êîëè÷åñòâà ïîñåùåííûõ îáúåêòîâ. Êà÷åñòâî ðåçóëüòàòîâ â çíà÷èòåëüíîé ñòåïåíè çàâèñèò îò òîãî, íàñêîëüêî ñõîäíû ñ áëèæàéøèì ñîñåäîì ñòàðòîâûå îáúåêòû. Â ðàáîòå [98] ïðåäëîæåíà ìîäèôèêàöèÿ ÈÑ ýòîãî êëàññà äëÿ áèíàðíûõ âåêòî- ðîâ, êîòîðàÿ ñòðîèò äîïîëíåííûé ãðàô ñîñåäñòâà. Îí ÿâëÿåòñÿ êîìáèíàöèåé ãðàôà ñîñåäñòâà âåêòîðîâ áàçû (êàæäûé âåêòîð áàçû ñîåäèíåí ñ áëèæàéøèìè ñîñåäÿìè) è ìîñòîâîãî ãðàôà (êàæäûé ìîñòîâîé âåêòîð ñîåäèíåí ñ áëèæàéøèìè ñîñåäÿìè áàçû). Ìîñòîâûå âåêòîðû íå ïðèíàäëåæàò áàçå, íî ÿâëÿþòñÿ õîðîøèìè ñòàðòîâûìè âåêòî- ðàìè. Èõ ôîðìèðóþò ñëåäóþùèì îáðàçîì. Âåêòîðû ðàçáèâàþò íà ÷àñòè. Âñå N âåê- òîðîâ ïîäâåðãàþò êëàñòåðèçàöèè íà K êëàñòåðîâ ïî êàæäîé èç M ÷àñòåé. Íà÷àëüíû- ìè öåíòðàìè ÿâëÿþòñÿ ñëó÷àéíûå âåêòîðû áàçû, çàòåì öåíòðû ìîäèôèöèðóþò íà- çíà÷åíèåì êîìïîíåíòó çíà÷åíèÿ, íàèáîëåå ÷àñòî âñòðå÷àþùåãîñÿ ó âåêòîðîâ êëàñòåðà (ñì. ðàçä. 4). Ìîñòîâîé âåêòîð (âñåãî èõ K M ) ÿâëÿåòñÿ êîìáèíàöèåé öåí- òðàëüíûõ âåêòîðîâ êëàñòåðîâ. Äëÿ ñîêðàùåíèÿ âû÷èñëåíèé ìîñòîâîé ãðàô ñòðîÿò ïðèáëèæåííî, âûáèðàÿ äëÿ êàæäîãî âåêòîðà áàçû 1000 áëèæàéøèõ ìîñòîâûõ, à çà- òåì äëÿ êàæäîãî ìîñòîâîãî 50 áëèæàéøèõ âåêòîðîâ áàçû. Ïðèáëèæåííûé ãðàô ñî- ñåäñòâà áàçû ñòðîÿò ïðèáëèæåííûì ïîèñêîì FLANN ([39] è ñì. ðàçä. 4). Ïðè ïîèñêå ïî äîïîëíåííîìó ãðàôó ñîñåäñòâà âíà÷àëå ïîìåùàþò â ïðèîðèòåò- íóþ î÷åðåäü ìîñòîâîé âåêòîð, áëèæàéøèé ê çàïðîñó. Íà êàæäîé èòåðàöèè, åñëè âåêòîð áàçû ïåðâûé â î÷åðåäè, åãî íåïîñåùåííûõ ñîñåäåé ïî ãðàôó ñîñåäñòâà ïîìå- ùàþò â î÷åðåäü. Åñëè ìîñòîâîé âåêòîð ïåðâûé â î÷åðåäè, â íåå ïîìåùàþò åãî ñîñå- äåé ïî ìîñòîâîìó ãðàôó, à òàêæå ñëåäóþùèé áëèæàéøèé ìîñòîâîé âåêòîð. Ïîêàçà- íî ïðåèìóùåñòâî ïî ñêîðîñòè ïîèñêà íàä FLANN è MIH ïðè áëèçêîé ê 1 òî÷íîñòè. 182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 Îòìåòèì, ÷òî ðàçíîâèäíîñòè ãðàôîâ ñîñåäñòâà, èçâåñòíûå êàê ãðàôû òåñíîãî ìèðà [99, 4], äåìîíñòðèðóþò íàèëó÷øèå ðåçóëüòàòû êàê ñðåäè ãðàôîâ ñîñåäñòâà, òàê è ñðåäè äðóãèõ ÈÑ. 6. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÍÀ ÎÑÍÎÂÅ ÍÅÉÐÎÑÅÒÅÂÎÉ ÀÂÒÎÀÑÑÎÖÈÀÒÈÂÍÎÉ ÏÀÌßÒÈ Ðàçíîâèäíîñòè àññîöèàòèâíîé ïàìÿòè [100] (èëè ïàìÿòè, àäðåñóåìîé ïî ñîäåð- æèìîìó) ìîæíî ðàññìàòðèâàòü êàê ÈÑ äëÿ íåêîòîðûõ òèïîâ ïîèñêà ïî ñõî- äñòâó. Â àâòîàññîöèàòèâíîé ïàìÿòè íà âûõîäå ïîëó÷àþò áèíàðíûé âåêòîð, íà- èáîëåå ñõîäíûé ñ âåêòîðîì íà âõîäå, ò.å. îíà âûïîëíÿåò çàïðîñ NN äëÿ áè- íàðíûõ âåêòîðîâ. Â ðàñïðåäåëåííîé ïàìÿòè ðàçëè÷íûå âåêòîðû õðàíÿò â îáùèõ ÿ÷åéêàõ ïàìÿ- òè. Íåéðîáèîëîãè÷åñêè ïðàâäîïîäîáíûå âàðèàíòû ðàñïðåäåëåííîé ïàìÿòè ìîæ- íî ïðåäñòàâèòü â âèäå èñêóññòâåííûõ íåéðîííûõ ñåòåé, â êîòîðûõ çàïîìèíàíèå âåêòîðà îáû÷íî âûïîëíÿåòñÿ çà îäíî åãî ïðåäúÿâëåíèå ëîêàëüíûì îáó÷àþùèì ïðàâèëîì, ìîäèôèöèðóþùèì âåñà ìåæíåéðîííûõ ñâÿçåé, à âîññòàíîâëåíèå âåê- òîðà ïàìÿòè â îòâåò íà âåêòîð-çàïðîñ îñóùåñòâëÿåòñÿ èòåðàòèâíîé ïðîöåäóðîé ðàñïðîñòðàíåíèÿ àêòèâíîñòè ìåæäó íåéðîíàìè ïî ñâÿçÿì. Ïîèñê îáû÷íî âûïîëíÿåòñÿ ïî sim dot . Êðàòêî ðàññìîòðèì íåéðîñåòåâûå âàðèàíòû ðàñïðåäåëåííîé àâòîàññîöèà- òèâíîé ïàìÿòè (îáîçíà÷èì åå Neural Associative Memory, NAM). Áîëåå ïîäðîá- íûé îáçîð ïðåäñòàâëåí â [100]. 6.1. Îáîáùåííàÿ ñõåìà è õàðàêòåðèñòèêè NAM. Áóäåì ðàññìàòðèâàòü, ãëàâíûì îáðàçîì, ðàñïðåäåëåííûå NAM ìàòðè÷íîãî òèïà, êîòîðûå ÿâëÿþòñÿ ïî- ëíîñâÿçíûìè ñåòÿìè áèíàðíûõ íåéðîíîâ. Êàæäûé èç D íåéðîíîâ ïðåäñòàâëÿåò êîìïîíåíò áèíàðíîãî âåêòîðà z ðàçìåðíîñòè D, ò.å. íåéðîí ìîæåò áûòü â ñîñòîÿ- íèè 0 èëè 1. Êàæäàÿ ïàðà íåéðîíîâ èìååò äâå âçàèìíûå ñâÿçè, ýëåìåíòû ìàòðè- öû ñâÿçåé W( )D D� ñîîòâåòñòâóþò âåñàì ñâÿçåé. Â ðåæèìå îáó÷åíèÿ âåêòîðû áàçû y «çàïîìèíàþò» â ìàòðèöå W, ïðèìåíÿÿ íåêîòîðûå «îáó÷àþùèå ïðàâèëà», êîòîðûå èçìåíÿþò çíà÷åíèÿ wij (èçíà÷àëüíî wij îáû÷íî íóëåâûå). Ïðè âûïîëíåíèè çàïðîñà íà ñåòü ïîäàþò áèíàðíûé âåêòîð x àêòèâàöèåé íå- éðîíîâ: z x� . Âû÷èñëÿþò âõîäíóþ ñóììó íåéðîíà x : s w zi j D ij j� �� 1 . Ñîñòîÿíèå íåéðîíà îïðåäåëÿþò êàê z ti ( )� �1 1(àêòèâåí) ïðè s t T ti i( ) ( )� è z ti ( )� �1 0 (íåàê- òèâåí) ïðè s t T ti i( ) ( )� , Ti — çíà÷åíèå ïîðîãà íåéðîíà. Ïðè ïàðàëëåëüíîé (ñèí- õðîííîé) äèíàìèêå ñåòè íà êàæäîì øàãå t îïðåäåëÿþò (îáíîâëÿþò) ñîñòîÿíèÿ âñåõ D íåéðîíîâ. Ïàðàìåòðû W, T óñòàíàâëèâàþò òàê, ÷òîáû ïîñëå îäíîãî èëè íåñêîëüêèõ øàãîâ äèíàìèêè ñåòü ïðèõîäèëà â ñòàáèëüíîå ñîñòîÿíèå. Â ýòîì ñîñòîÿíèè âåêòîð z — âûõîä ñåòè. Âåêòîð-çàïðîñ x — îáû÷íî èñêàæåííûé âåêòîð áàçû. Åñëè êîëè÷åñòâî çàïîì- íåííûõ âåêòîðîâ íå ñëèøêîì âåëèêî, âûõîä z ÿâëÿåòñÿ çàïîìíåííûì âåêòîðîì áàçû y, áëèæàéøèì ê x ïî sim dot ( , )x y , ò.å. NAM âîçâðàùàåò òî÷íîãî NN. Ñëîæíîñòü (âðåìÿ âûïîëíåíèÿ) îäíîãî øàãà äèíàìèêè ñåòè O D( )2 . Ïîýòîìó, åñëè â NAM óäà- åòñÿ çàïîìíèòü N D� âåêòîðîâ ñ âîçìîæíîñòüþ âîññòàíîâëåíèÿ èç èñêàæåííûõ âåðñèé, âðåìÿ âûïîëíåíèÿ çàïðîñà ìîæåò îêàçàòüñÿ ìåíüøèì O DN( ). Òàê êàê çà- òðàòû ïàìÿòè ýòîãî òèïà NAM O D( )2 , ñ ðîñòîì D âîçìîæíî óâåëè÷åíèå êîëè÷åñò- âà N âåêòîðîâ, êîòîðîå ìîæåò áûòü çàïîìíåíî è âîññòàíîâëåíî. Ê ñîæàëåíèþ, âåêòîð íà âûõîäå NAM ìîæåò íå ÿâëÿòüñÿ áëèæàéøèì ñîñå- äîì âåêòîðà-çàïðîñà, è äàæå âåêòîðîì áàçû. Êðîìå òîãî, èíîãäà â NAM óäàåòñÿ âîññòàíîâèòü òîëüêî N D�� âåêòîðîâ, îñîáåííî åñëè âåêòîðû-çàïðîñû ñèëüíî èñêàæåíû. Â êà÷åñòâå âåêòîðîâ áàçû çà÷àñòóþ ðàññìàòðèâàþò áèíàðíûå âåêòîðû, ñëó- ÷àéíî âûáðàííûå èç íåêîòîðîãî ðàñïðåäåëåíèÿ (íàïðèìåð, âåêòîðû ñ âåðîÿòíîñ- òüþ p �1 2/ ëèáî p� 1 2/ êîìïîíåíòîâ ñî çíà÷åíèÿìè 1). Âåêòîðû-çàïðîñû ÿâëÿ- þòñÿ èñêàæåííûìè âåêòîðàìè áàçû. Èñêàæåíèå óäàëåíèåì ñëó÷àéíî ñòèðàåò ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 183 ÷àñòü åäèíè÷íûõ êîìïîíåíòîâ âåêòîðà áàçû (îñòàëüíûå êîìïîíåíòû ãàðàíòèðî- âàííî ñîâïàäàþò). Áîëåå ñëîæíîå äëÿ ïîèñêà èñêàæåíèå øóìîì ñëó÷àéíî óäàëÿ- åò è äîáàâëÿåò åäèíè÷íûå êîìïîíåíòû ñ ñîõðàíåíèåì (òî÷íûì èëè ïðèáëèæåí- íûì) èõ îáùåãî êîëè÷åñòâà. Îòìåòèì, ÷òî ïîñëåäíåå ðàñïðåäåëåíèå èçâåñòíî êàê the light bulb problem [101] è åãî èññëåäóþò â LSH [83, 86]. Ïðè çàïîìèíàíèè ñëèøêîì áîëüøîãî êîëè÷åñòâà âåêòîðîâ NAM «ïåðåãðóæà- åòñÿ» è ïåðåñòàåò âûïîëíÿòü ôóíêöèþ àâòîàññîöèàòèâíîé ïàìÿòè. Çíà÷åíèå N , ïðè êîòîðîì NAM ïðîäîëæàåò âîññòàíàâëèâàòü âåêòîð, çàâèñèò îò åå êîíñòðóê- öèè, ðàñïðåäåëåíèÿ âåêòîðîâ áàçû è çàïðîñîâ, ñòåïåíè èñêàæåíèÿ âåêòîðîâ-çàïðî- ñîâ. ×àñòî èññëåäóþò èíôîðìàöèîííûå õàðàêòåðèñòèêè NAM (â òåðìèíàõ èíôîð- ìàöèè Øåííîíà, êîòîðàÿ çàïîìèíàåòñÿ è èçâëåêàåòñÿ èç NAM, è åå ìàêñèìàëüíûõ çíà÷åíèé), èç íèõ ìîæíî îïðåäåëèòü õàðàêòåðèñòèêè â òåðìèíàõ N . 6.2. Cåòè Hopfield. Â NAM Hopfield [102] èñïîëüçóþò «ïëîòíûå» ñëó÷àéíûå áèíàðíûå âåêòîðû (ñ êîìïîíåíòàìè èç {0,1} ñ âåðîÿòíîñòüþ p �1 2/ åäèíè÷íîãî çíà÷åíèÿ). Ïðîöåäóðà îáó÷åíèÿ ôîðìèðóåò (ñèììåòðè÷íóþ) W ïîî÷åðåäíûì çà- ïîìèíàíèåì âåêòîðîâ áàçû y ïî ïðàâèëó Hopfield: w w y p y pij ij i j� � � �( )( ), p �1 2/ , wii � 0. Äèíàìèêà âîññòàíîâëåíèÿ â [102] ïîñëåäîâàòåëüíàÿ ñ ïîðîãîì T � 0 (âî ìíîãèõ ïîñëåäóþùèõ èññëåäîâàíèÿõ è ðåàëèçàöèÿõ äèíàìèêà ïàðàë- ëåëüíàÿ). Ïîêàçàíî [102], ÷òî òàêàÿ ñåòü ïðèõîäèò â óñòîé÷èâîå ñîñòîÿíèå, ïðè- ÷åì äî N D� 014. çàïîìíåííûì âåêòîðàì ñîîòâåòñòâóþò óñòîé÷èâûå ñîñòîÿíèÿ, ïðè ìåíüøèõ N âîçìîæíî âîññòàíîâëåíèå èñêàæåííûõ âåêòîðîâ. Ñõîäíûå ðå- çóëüòàòû ïîëó÷åíû êàê àñèìïòîòè÷åñêè (ïðè D � �), òàê è ïðè êîíå÷íûõ D. Äëÿ ñëó÷àéíûõ ðàçðåæåííûõ âåêòîðîâ (ïðè p� 1 2/ ) â ñåòè Hopfield äîñòèæèìû ëó÷øèå õàðàêòåðèñòèêè, ÷åì ïðè p �1 2/ [103]. Íàïðèìåð, âîññòàíîâëåíèå ìîæåò âûïîëíÿòüñÿ è ïðè N D�� . Çíà÷åíèå ïîðîãà T t( ) â ýòîì ñëó÷àå âûáèðàþò ïîëîæè- òåëüíûì, íàïðèìåð òàêèì, ÷òîáû îáåñïå÷èòü pD àêòèâíûõ íåéðîíîâ ïðè ïàðàëëåëü- íîé äèíàìèêå. Äåòàëüíûå òåîðåòè÷åñêèå è ýêñïåðèìåíòàëüíûå èññëåäîâàíèÿ èíôîð- ìàöèîííûõ õàðàêòåðèñòèê ñåòè Hopfield ïðè ðàçëè÷íûõ èñêàæåíèÿõ âõîäíîãî âåêòî- ðà è D p N, , [104, 105] ïîêàçàëè, ÷òî èñïîëüçîâàííûå ìåòîäû òåîðåòè÷åñêîãî àíàëèçà ïëîõî ïðåäñêàçûâàþò õàðàêòåðèñòèêè êîíå÷íûõ ñåòåé äëÿ ìàëûõ pD. Íàè- ëó÷øèå õàðàêòåðèñòèêè â òåðìèíàõ èçâëåêàåìîé èç ñåòè èíôîðìàöèè ïîëó÷åíû ïðè p � 0.001–0.01, ÷òî ñîîòâåòñòâóåò àêòèâíîñòè íåéðîíîâ ìîçãà. Â [106–108] îöåíèâàþò êîëè÷åñòâî âåêòîðîâ ïàìÿòè, êîòîðûå ÿâëÿþòñÿ óñòîé÷èâûìè ñîñòîÿíèÿìè, à òàêæå ìîãóò áûòü âîññòàíîâëåíû èç èñêàæåííûõ øóìîì âåêòîðîâ-çàïðîñîâ êàê ïðîïîðöèîíàëüíîå ( / ln )D D 2 ïðè p D D� ln / (àñèìïòîòè÷åñêè, ò.å. ïðè D � � , ñî ñòðåìÿùåéñÿ ê 1 âåðîÿòíîñòüþ). Åñëè àï- ïðîêñèìèðîâàòü êîëè÷åñòâî øàãîâ âîñïðîèçâåäåíèÿ êàê ln D, óñêîðåíèå ïîèñêà ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì ñîñòàâëÿåò ïîðÿäêà D D/ (ln )3 . Èññëåäîâàíèå â [109] ïðèâåëî àâòîðîâ ê âûâîäó î âîçìîæíîñòè óñêîðåíèÿ ïîèñêà ñ ïîìîùüþ ñåòè Hopfield ïî ñðàâíåíèþ ñ äðóãèìè ÈÑ äëÿ ìàëûõ p è áîëüøèõ D N, . 6.3. Cåòè Willshaw. Â àâòîàññîöèàòèâíîì âàðèàíòå NAM Willshaw [110–112] ñâÿçè áèíàðíûå èç { , }0 1 . Ïðàâèëî îáó÷åíèÿ Willshaw: w w y yij ij i j� � �( ), ãäå � — äèçúþíêöèÿ, � — êîíúþíêöèÿ. Â îòëè÷èå îò ñåòè Hopfield ïðè ïîñòîÿííîì p è ðîñòå N ïðîïîðöèîíàëüíî D ñåòü Willshaw ïåðåñòàåò ðàáîòàòü, òàê êàê âñå ñâÿçè ñòàíîâÿòñÿ åäèíè÷íûìè. Ïîýòîìó èñïîëüçóþò p D D~ ln / . Èç àíàëèòè÷åñêîãî è ýêñïåðèìåíòàëüíîãî èññëåäîâàíèé [113, 114] ñëåäóåò, ÷òî â îòëè÷èå îò ñåòè Hopfield, â êîòîðîé èíôîðìàöèîííûå õàðàêòåðèñòèêè (ñì. [100]) ìîíîòîííî ðàñòóò ñ D , â ñåòè Willshaw äëÿ íå ñëèøêîì áîëüøèõ D èõ çíà÷åíèÿ áîëüøå, ÷åì ïðè D � � . Âñëåäñòâèå áèíàðíîñòè ñâÿçåé óäåëüíûå õà- ðàêòåðèñòèêè (íà áèò ïàìÿòè) ëó÷øèå, ÷åì ó ñåòè Hopfield. 6.4. Ñåòè Potts. Â ðàáîòàõ [115–117] NAM ðàññìàòðèâàåòñÿ êàê ñåòü íåéðî- íîâ, êîòîðûå ðàçáèòû íà ~ ln D íå ïåðåñåêàþùèõñÿ ÷àñòåé («êîëîíîê»), â êàæäîé êîëîíêå òîëüêî îäèí àêòèâíûé íåéðîí. Äëÿ îáó÷åíèÿ èñïîëüçóþò ïðàâèëî Hopfield, à òàêæå Willshaw [118, 119]. Ìåæäó íåéðîíàìè â êîëîíêå íå ñóùåñòâó- 184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 åò ñâÿçåé. Äèíàìèêà ñåòè àêòèâèðóåò â êàæäîé êîëîíêå îäèí íåéðîí ñ ìàêñè- ìàëüíîé âõîäíîé ñóììîé. Ñîãëàñíî [118] èíôîðìàöèîííûå õàðàêòåðèñòèêè ïî- äîáíû ñåòè Willshaw ïðè àíàëîãè÷íîé ðàçðåæåííîñòè âåêòîðîâ. Àíàëèòè÷åñêîå è ýêñïåðèìåíòàëüíîå ñðàâíåíèÿ ñåòåé Hopfield, Willshaw, Potts ñ ïðàâèëîì Willshaw äëÿ âåêòîðîâ ñ p D D~ ln / è èñêàæåíèÿìè âåêòî- ðîâ-çàïðîñîâ óäàëåíèåì ïðîâåäåíî â [108]. Òåîðåòè÷åñêè èññëåäóþò âîññòàíîâ- ëåíèå çà îäèí øàã (àñèìïòîòè÷åñêè, ò.å. ïðè D � � , ñî ñòðåìÿùåéñÿ ê 1 âåðîÿò- íîñòüþ). Äëÿ âñåõ ìîäåëåé ïîëó÷åíà íèæíÿÿ ãðàíèöà N ïîðÿäêà ( / ln )D D 2 , à äëÿ ñåòè Willshaw ïîêàçàíî ñîâïàäåíèå ñ âåðõíåé ãðàíèöåé. Îòìåòèì, ÷òî ôóíêöèè NAM âûïîëíÿþòñÿ è â íåïîëíîñâÿçíûõ ñåòÿõ êàê äëÿ ïëîòíûõ, òàê è äëÿ ðàçðåæåííûõ âåêòîðîâ (íàïðèìåð, [120, 121]). Ýòî ìîæíî èñ- ïîëüçîâàòü äëÿ óìåíüøåíèÿ çàòðàò ïàìÿòè NAM ñ êâàäðàòè÷íûõ äî ëèíåéíûõ îò D. 6.5. Äðóãèå íàïðàâëåíèÿ â NAM. Çàñëóæèâàþò âíèìàíèÿ ÈÑ äëÿ óñêîðå- íèÿ ïîèñêà ïî ñõîäñòâó, â êîòîðûõ ìîäóëè NAM èñïîëüçóþòñÿ íà îòäåëüíûõ ýòàïàõ ïîèñêà. Â [122] ÈÑ ïðèìåíÿþò íåñêîëüêî NAM äëÿ çàïîìèíàíèÿ ÷àñòåé áàçû, à ñõîäñòâî ðåçóëüòàòà îäíîøàãîâîãî âîñïðîèçâåäåíèÿ NAM ñ çàïðîñîì èñ- ïîëüçóþò äëÿ âûáîðà «ëó÷øåé» NAM äëÿ âûïîëíåíèÿ òî÷íîãî ëèíåéíîãî ïîèñ- êà ïî åå âåêòîðàì. Ðåàëüíûå äàííûå âî ìíîãèõ ñëó÷àÿõ íå ÿâëÿþòñÿ áèíàðíûìè ðàçðåæåííûìè âåêòîðàìè áîëüøîé ðàçìåðíîñòè, ñ êîòîðûìè ëó÷øå âñåãî ðàáîòàþò ðàññìîòðåí- íûå NAM. Ïîýòîìó òðåáóþòñÿ ñîõðàíÿþùèå ñõîäñòâî ïðåîáðàçîâàíèÿ ïðåäñòàâ- ëåíèé ðàçëè÷íîãî òèïà â ýòîò ôîðìàò (ñì. îáçîðû â [16, 17, ïîäðàçä. 5.1]). Îäíà- êî ïîëó÷åííûå âåêòîðû (êàê è èñõîäíûå ðåàëüíûå äàííûå) íå ÿâëÿþòñÿ ñëó÷àé- íûìè è íåçàâèñèìûìè, ïîýòîìó àíàëèòè÷åñêèå è ýêñïåðèìåíòàëüíûå ðåçóëüòàòû, èìåþùèåñÿ â îñíîâíîì äëÿ òàêèõ âåêòîðîâ, îáû÷íî íå ìîãóò ïðåä- ñêàçûâàòü õàðàêòåðèñòèêè NAM äëÿ ðåàëüíûõ äàííûõ. Â NAM ðàññìîòðåííîãî òèïà âîçíèêàåò ôóíêöèÿ, îòëè÷íàÿ îò ôóíêöèè àñ- ñîöèàòèâíîé ïàìÿòè, êîòîðàÿ ìîæåò ðàññìàòðèâàòüñÿ êàê ôóíêöèÿ îáîáùå- íèÿ [100]. Äàæå ïðè çàïîìèíàíèè ñëó÷àéíûõ âåêòîðîâ â íåéðîñåòè âîçíèêàþò äîïîëíèòåëüíûå óñòîé÷èâûå ñîñòîÿíèÿ. Äëÿ êîððåëèðîâàííûõ âåêòîðîâ íåéðî- íû, ïðåäñòàâëÿþùèå èõ îáùèå åäèíè÷íûå êîìïîíåíòû, ñòàíîâÿòñÿ «òåñíî» ñâÿ- çàííûìè, ÷òî ïðèâîäèò ê âîçíèêíîâåíèþ óñòîé÷èâîãî ñîñòîÿíèÿ ñåòè, ñîîòâå- òñòâóþùåãî ýòèì êîìïîíåíòàì. Âûÿâëåíèå òàêèõ ñîñòîÿíèé ìîæíî èñïîëüçîâàòü äëÿ àíàëèçà äàííûõ (íàïðèìåð äëÿ áèíàðíîãî ôàêòîðíîãî àíàëèçà [123]) è êàê ìîäåëü îáîáùåíèÿ èíôîðìàöèè â ìîçãå, âêëþ÷àÿ ïîÿâëåíèå èåðàðõèé êàòåãîðèçàöèè [100]. Â NAM ñî ñâÿçÿìè âûñîêèõ ïîðÿäêîâ n � 2 [124–128] ñâÿçè èìåþòñÿ íå ìåæ- äó ïàðîé (n � 2), à ìåæäó áîëüøèì êîëè÷åñòâîì íåéðîíîâ n. Òàêèå NAM ïîçâîëÿ- þò çàïîìíèòü êîëè÷åñòâî ïëîòíûõ âåêòîðîâ, ïðîïîðöèîíàëüíîå D n�1, îäíàêî ýòî äîñòèãàåòñÿ ñîîòâåòñòâóþùèì óâåëè÷åíèåì êîëè÷åñòâà ñâÿçåé, à çíà÷èò, ïà- ìÿòè è âðåìåíè îáðàáîòêè. Îáîáùåíèå ýòîãî òèïà NAM [126, 127] ïîçâîëÿåò ïðîâåñòè èíòåðåñíûå àíàëîãèè ñ ïåðñåïòðîíàìè è ÿäåðíûìè ìåòîäàìè â çàäà÷å êëàññèôèêàöèè. Îäíàêî äëÿ ïîèñêà NN âðåìÿ çàïðîñà ëèíåéíî îò N . Â ïîñëåäíåå âðåìÿ ïîÿâèëèñü [129–132] àâòîàññîöèàòèâíûå NAM ñî ñòðóê- òóðîé äâóäîëüíîãî ãðàôà, ãäå ìàòðèöû ñâÿçåé çàäàþò ëèíåéíûå îãðàíè÷åíèÿ, íà- ëàãàåìûå íà (íåáèíàðíûå) âåêòîðû. Îíè ïîçâîëÿþò âîññòàíàâëèâàòü N D~ exp( ) âåêòîðîâ. Îäíàêî ýòî ñïðàâåäëèâî äëÿ äàííûõ èç ìîäåëåé, êîòîðûì ðåàëüíûå äàííûå çà÷àñòóþ íå ñîîòâåòñòâóþò. Îòìåòèì, ÷òî ðàçíîâèäíîñòè ñåòè Hopfield èñïîëüçóþò äëÿ îïòèìèçàöèè (ñì., íàïðèìåð, ïóáëèêàöèè [133, 134] è ññûëêè ê íèì). ÇÀÊËÞ×ÅÍÈÅ Ðàññìàòðèâàåìûå â ðàçä. 2–5 ÈÑ ïðè êîíñòðóèðîâàíèè ðàçáèâàþò ìíîæåñòâî îáúåêòîâ áàçû íà ïîäìíîæåñòâà, îáû÷íî íå ïåðåñåêàþùèåñÿ. Ïðè âûïîëíåíèè ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 185 çàïðîñà ïîèñêà ïî ñõîäñòâó áûñòðî îïðåäåëÿþò «ïåðñïåêòèâíûå» ïîäìíîæåñ- òâà, èñïîëüçóþò èõ îáúåêòû â êà÷åñòâå êàíäèäàòîâ, îòâåò íà çàïðîñ ïîëó÷àþò âû÷èñëåíèåì ðàññòîÿíèé/ñõîäñòâ êàíäèäàòîâ äî îáúåêòà-çàïðîñà è ïðèíÿòèåì ðåøåíèÿ î âêëþ÷åíèè íóæíûõ êàíäèäàòîâ â ìíîæåñòâî îáúåêòîâ-îòâåòîâ. Ïðèìåíåíèå íåñêîëüêèõ íåçàâèñèìûõ ÈÑ óëó÷øàåò ðåçóëüòàòû ïîèñêà. Åñëè îáùåå êîëè÷åñòâî êàíäèäàòîâ ìåíüøå êîëè÷åñòâà îáúåêòîâ áàçû N , âîçìîæíî óñêîðåíèå ïîèñêà îòíîñèòåëüíî ëèíåéíîãî ïîèñêà. Â ÈÑ íà îñíîâå õýø-òàáëèö (ñì. ðàçä. 2, 3) çíà÷åíèå õýøà îáúåêòà îïðåäåëÿ- åò êîðçèíó ÈÑ, êîòîðîé îí ïðèíàäëåæèò. Â îòëè÷èå îò îáû÷íîãî õýøèðîâàíèÿ, ãäå çíà÷åíèÿ õýøåé ñòðåìÿòñÿ ñäåëàòü ðàçëè÷íûìè äëÿ ðàçëè÷íûõ îáúåêòîâ, èñ- ïîëüçóþò õýøèðîâàíèå, êîòîðîå ñõîäíûì îáúåêòàì ãåíåðèðóåò îäèíàêîâûå õýø-çíà÷åíèÿ. Ïðè ïîèñêå îáúåêòû-êàíäèäàòû èçâëåêàþòñÿ èç êîðçèíû, ñîîòâåòñòâóþùåé õýøó îáúåêòà-çàïðîñà. Äëÿ áèíàðíûõ âåêòîðîâ â êà÷åñòâå õýøà ìîæåò íåïîñðåäñòâåííî èñïîëüçî- âàòüñÿ ñîâîêóïíîñòü çíà÷åíèé íåêîòîðîãî ïîäìíîæåñòâà èõ êîìïîíåíòîâ. Åñëè ïîäìíîæåñòâî âêëþ÷àåò âñå êîìïîíåíòû âåêòîðà, â êîðçèíå êàæäîãî âåêòîðà áàçû ñîäåðæèòñÿ îäèí ýòîò âåêòîð. ×òîáû íàéòè âñå âåêòîðû áàçû ñ dist Ham îò âåêòî- ðà-çàïðîñà, íå ïðåâûøàþùåì çàäàííîãî ðàäèóñà, âûïîëíÿþò ìíîæåñòâî çàïðîñîâ íà ñîâïàäåíèå. Âåêòîð-çàïðîñ â êàæäîì òàêîì çàïðîñå ïîëó÷àþò èç èñõîäíîãî, èç- ìåíÿÿ çíà÷åíèÿ íåêîòîðûõ åãî êîìïîíåíòîâ (÷èñëî èçìåíÿåìûõ êîìïîíåíòîâ âåê- òîðà âàðüèðóåòñÿ îò íóëÿ äî âåëè÷èíû ðàäèóñà). Êîëè÷åñòâî çàïðîñîâ íà ñîâïàäå- íèå, òðåáóþùèõñÿ äëÿ òî÷íîãî âûïîëíåíèÿ èñõîäíîãî çàïðîñà, áûñòðî ðàñòåò ñ óâåëè÷åíèåì ðàçìåðíîñòè âåêòîðîâ è ðàäèóñà è ìîæåò ïðåâûñèòü N . Ïîýòîìó â ÈÑ, ðàññìîòðåííûõ â ðàçä. 2, êîìïîíåíòû âåêòîðîâ ðàçáèâàþò íà íåïåðåñåêàþ- ùèåñÿ ÷àñòè (ïîäìíîæåñòâà) è äëÿ êàæäîé ÷àñòè êîíñòðóèðóþò ñâîþ òàáëè÷íóþ ÈÑ, â êîòîðîé íàõîäÿòñÿ âñå N âåêòîðîâ áàçû. Ýòî óìåíüøàåò ðàçìåðíîñòü è ïî- çâîëÿåò óìåíüøèòü ðàäèóñ ìîäèôèêàöèè êàæäîé ÷àñòè (èíîãäà ìîäèôèêàöèè ÷àñ- òè íå òðåáóåòñÿ) ñ ñîõðàíåíèåì ãàðàíòèé èçâëå÷åíèÿ èç âñåõ ÷àñòè÷íûõ ÈÑ êàíäè- äàòîâ, ñîäåðæàùèõ òî÷íûé îòâåò íà èñõîäíûé çàïðîñ. Òàêîé ïîäõîä ïîçâîëÿåò ñî- çäàâàòü ÈÑ äëÿ òî÷íîãî ïîèñêà ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè äëÿ äàííûõ ñðåäíåãî ñëó÷àÿ. ×àñòü òàêèõ ÈÑ ðàáîòàåò òîëüêî äëÿ ôèêñèðîâàííîãî ðàäèóñà çà- ïðîñà, äðóãèå ïîçâîëÿþò èçìåíÿòü ðàäèóñ. Â ÈÑ íà îñíîâå LSH-õýøèðîâàíèÿ (ñì. ðàçä. 3) LSH-ôóíêöèÿ íàçíà÷àåò îäè- íàêîâûå õýø-çíà÷åíèÿ ñõîäíûì îáúåêòàì ñ áîëüøåé âåðîÿòíîñòüþ, ÷åì íåñõîä- íûì. Ïîýòîìó â îäíîé êîðçèíå íàõîäÿòñÿ, â îñíîâíîì, ñõîäíûå îáúåêòû. Â áàçî- âîì âàðèàíòå ÈÑ LSH ñîñòîèò èç íàáîðà õýø-òàáëèö, äëÿ êàæäîé èñïîëüçóåòñÿ ñâîÿ ðåàëèçàöèÿ LSH-ôóíêöèè (çàäàþùàÿ èñ÷åðïûâàþùåå ðàçáèåíèå ïðîñòðà- íñòâà íà íåïåðåñåêàþùèåñÿ îáëàñòè). Â êàæäîé òàáëèöå íàõîäÿòñÿ ññûëêè íà âñå îáúåêòû áàçû, îáúåêò ïðèíàäëåæèò îäíîé êîðçèíå. Ïðè âûïîëíåíèè çàïðîñà èç- âëåêàþò êàíäèäàòîâ èç îäíîé êîðçèíû (ñîîòâåòñòâóþùåé õýøó îáúåêòà-çàïðîñà) êàæäîé òàáëèöû. Èñïîëüçîâàíèå ìíîæåñòâà òàáëèö ñíèæàåò âåðîÿòíîñòü ïîòåðè îáúåêòà, êîòîðûé ÿâëÿåòñÿ îòâåòîì íà çàïðîñ. Ãàðàíòèè ñóáëèíåéíîãî âðåìåíè äëÿ íåêîòîðûõ òèïîâ çàïðîñîâ ïðèáëèæåí- íîãî ïîèñêà äëÿ äàííûõ õóäøåãî ñëó÷àÿ äàþò ÈÑ LSH. Ê ïðåèìóùåñòâàì ÈÑ LSH òàêæå îòíîñèòñÿ âîçìîæíîñòü ñîçäàíèÿ ÈÑ äëÿ ðàçëè÷íûõ ìåð ðàññòîÿ- íèÿ/ñõîäñòâà (äëÿ êîòîðûõ ðàçðàáîòàíû LSH-ôóíêöèè). Òàê, äëÿ dist Ham èñïîëü- çóþò ïîäìíîæåñòâî êîìïîíåíòîâ âåêòîðîâ, îäíàêî â îòëè÷èå îò ÈÑ, ðàññìîòðåí- íûõ â ðàçä. 2, îíè âûáèðàþòñÿ ñëó÷àéíûì ñýìïëèðîâàíèåì ñ çàìåùåíèåì, ïîýòî- ìó ìîãóò ñîäåðæàòü îäèíàêîâûå êîìïîíåíòû. Ê LSH äëÿ áèíàðíûõ ðàçðåæåííûõ âåêòîðîâ îòíîñèòñÿ LSH äëÿ sim Jac. Íåäîñòàòêîì ÈÑ LSH ÿâëÿåòñÿ íåîáõîäè- ìîñòü ðàñ÷åòà è ñîçäàíèÿ îòäåëüíîé ìíîãîòàáëè÷íîé ÈÑ äëÿ êàæäîé êîìáèíà- öèè ðàäèóñà çàïðîñà è ñòåïåíè àïïðîêñèìàöèè (÷òîáû âûïîëíÿëèñü ãàðàíòèè, ýìïèðè÷åñêè õîðîøèå ðåçóëüòàòû ìîãóò äàâàòü ÈÑ LSH áåç òàêîãî ðàñ÷åòà). Êðîìå òîãî, ïîèñê äîïóñêàåò âåðîÿòíîñòü ïîòåðè îáúåêòîâ, êîòîðûå ÿâëÿþòñÿ îòâåòàìè íà çàïðîñ (false negatives). 186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 Â ðåçóëüòàòå óñîâåðøåíñòâîâàíèÿ LSH âîçìîæåí ïîèñê áåç ïîòåðü, íî ñ ãà- ðàíòèÿìè òîëüêî äëÿ ñðåäíåãî ñëó÷àÿ. Ðàçâèòèÿ LSH íà îñíîâå LSF èñïîëüçóþò íåòàáëè÷íûå ñòðóêòóðû, ïîçâîëÿþò äîáèòüñÿ ãèáêèõ êîìïðîìèññîâ çàòðàò âðå- ìåíè è ïàìÿòè è óëó÷øåíèÿ õàðàêòåðèñòèê LSH äëÿ íåêîòîðûõ ïàðàìåòðîâ. Âà- ðèàíòû LSH, çàâèñèìûå îò äàííûõ, íàïðàâëåíû íà óñêîðåíèÿ ïîèñêà äëÿ äàííûõ õóäøåãî ñëó÷àÿ. Â äðåâîâèäíûõ ÈÑ (ñì. ðàçä. 4) ïîäìíîæåñòâàì îáúåêòîâ áàçû ñîîòâåòñòâó- þò èåðàðõè÷åñêè îðãàíèçîâàííûå îáëàñòè, îáû÷íî íå ïåðåñåêàþùèåñÿ íà îäíîì óðîâíå èåðàðõèè. Ïîñëåäíÿÿ ïîçâîëÿåò áûñòðî ñòðîèòü áîëüøîå êîëè÷åñòâî ìà- ëûõ îáëàñòåé ÈÑ è îïðåäåëÿòü ïðèíàäëåæíîñòü ê íèì îáúåêòîâ. Ïðè ïîèñêå áëè- æàéøåãî ñîñåäà ñïóñêîì èç êîðíÿ â ëèñò íàõîäÿò ëèñòîâóþ îáëàñòü, êîòîðîé ïðèíàäëåæèò âåêòîð-çàïðîñ. Îáúåêòû áàçû ýòîé îáëàñòè îáû÷íî ÿâëÿþòñÿ õîðî- øèìè êàíäèäàòàìè íà áëèæàéøèõ ñîñåäåé (èëè íåïîñðåäñòâåííî ñîäåðæàò òî÷- íûõ ñîñåäåé). Îäíàêî äëÿ ãàðàíòèè òî÷íîãî ïîèñêà èññëåäóþò âñå äðóãèå ëèñòî- âûå îáëàñòè, êîòîðûå ìîãóò ñîäåðæàòü òî÷íûé îòâåò. Òàêèõ îáëàñòåé ìîæåò áûòü ìíîãî, îñîáåííî â ìíîãîìåðíûõ ïðîñòðàíñòâàõ, ÷òî çàìåäëÿåò ïîèñê. Îäíà- êî îáúåêòû â íèõ îáû÷íî ëèøü íåçíà÷èòåëüíî óëó÷øàþò (èëè âîîáùå íå èçìåíÿ- þò) êà÷åñòâî îòâåòîâ. Ïîýòîìó äëÿ áûñòðîãî ïðèáëèæåííîãî ïîèñêà áëèæàéøèõ ñîñåäåé îãðàíè÷èâàþò êîëè÷åñòâî ïðîñìàòðèâàåìûõ îáëàñòåé (âïëîòü äî îäíîé, êîòîðîé ïðèíàäëåæèò çàïðîñ), à êà÷åñòâî ðåçóëüòàòîâ óëó÷øàþò, ïðèìåíÿÿ ìíîæåñòâà ÈÑ ñ ðàçëè÷íûìè ðàçáèåíèÿìè. Ïðè ýòîì íå èìååòñÿ ñòðîãèõ ãàðàíòèé êà÷åñòâà ðåçóëüòàòîâ, íî ýìïèðè÷åñêèå ðåçóëüòàòû õîðîøèå. Îáùèì íåäîñòàòêîì ÈÑ, ðàññìîòðåííûõ â ðàçä. 2–4, ÿâëÿåòñÿ íåîáõîäè- ìîñòü èñïîëüçîâàíèÿ íåñêîëüêèõ ÈÑ ñ ñîîòâåòñòâóþùèìè çàòðàòàìè ïàìÿòè. Â ÈÑ íà îñíîâå ãðàôîâ ñîñåäñòâà (ñì. ðàçä. 5) äëÿ êàæäîãî îáúåêòà áàçû ñî- õðàíÿþò ñïèñîê îáúåêòîâ åãî îêðåñòíîñòè. Ìíîæåñòâà îáúåêòîâ îêðåñòíîñòåé ñîñåäíèõ îáúåêòîâ ïåðåñåêàþòñÿ. Ïðè âûïîëíåíèè çàïðîñà ïðèáëèæåííîãî ïîèñ- êà áëèæàéøèõ ñîñåäåé ñòàðòóþò ñ íåêîòîðîãî îáúåêòà è ïåðåõîäÿò íà åùå íåïî- ñåùåííûé îáúåêò èç åãî îêðåñòíîñòè, íàèáîëåå áëèçêèé ê îáúåêòó-çàïðîñó, ïîêà òàêèå îáúåêòû èìåþòñÿ. Ðåñòàðò ïîèñêà ñ äðóãèõ îáúåêòîâ ÿâëÿåòñÿ àíàëîãîì èñ- ïîëüçîâàíèÿ íåñêîëüêèõ ÈÑ. Ê ïðåèìóùåñòâàì òàêèõ ÈÑ îòíîñèòñÿ âûñîêàÿ ñêî- ðîñòü è êà÷åñòâî ïðèáëèæåííîãî ïîèñêà, ê íåäîñòàòêàì — ñëîæíîñòü ïîñòðîåíèÿ è îòñóòñòâèå ãàðàíòèé êà÷åñòâà ïîèñêà. Ðàçìåðíîñòè âåêòîðîâ, ñ êîòîðûìè íà ïðàêòèêå ðàáîòàþò ÈÑ, íåâåëèêè. Òàê, äëÿ òî÷íîãî ïîèñêà ïëîòíûõ (áèíàðíûõ) âåêòîðîâ îíè íå ïðåâûøàþò äåñÿòêîâ èëè ñîòåí, äëÿ ïðèáëèæåííîãî ïîèñêà — òûñÿ÷è, ïðè ðàäèóñå çàïðîñà äî ÷åòâåð- òè ðàçìåðíîñòè, à îáû÷íî ãîðàçäî ìåíüøå. Ïîèñê äëÿ ðàçðåæåííûõ (áèíàðíûõ) âåêòîðîâ áîëüøîé ðàçìåðíîñòè âûïîëíÿåòñÿ, â îñíîâíîì, ñ ïîìîùüþ îáðàòíîãî èíäåêñà, LSH äëÿ sim Jac è sim BB, à òàêæå ÈÑ, ðàññìîòðåííûõ â ðàçä. 6. ßâëÿÿñü ìîäåëüþ áèîëîãè÷åñêîé ïàìÿòè, íåéðîñåòåâàÿ ðàñïðåäåëåííàÿ àâòîàñ- ñîöèàòèâíàÿ ïàìÿòü (NAM, ñì. ðàçä. 6) ìîæåò ðàññìàòðèâàòüñÿ è êàê ÈÑ äëÿ ïîèñêà ïî ñõîäñòâó, çíà÷èòåëüíî îòëè÷àþùàÿñÿ îò òðàäèöèîííûõ ÈÑ äðóãèõ òèïîâ. Â äàí- íîì ñëó÷àå íå èñïîëüçóþòñÿ õðàíåíèå îòäåëüíûõ âåêòîðîâ áàçû, ðàçáèåíèå áàçû íà ïîäìíîæåñòâà, äâóõýòàïíàÿ ñòðàòåãèÿ ôèëüòðàöèè è óòî÷íåíèÿ ïðè âûïîëíåíèè çà- ïðîñà. Ïîèñê âîçâðàùàåò òîëüêî îäèí âåêòîð, êîòîðûé âîññòàíàâëèâàåòñÿ íà âûõîäå ÈÑ èòåðàòèâíî, íî ìîæåò íå ÿâëÿòüñÿ âåêòîðîì áàçû. Â ðàñïðåäåëåííûõ NAM N âåêòîðîâ áàçû ðàñïðåäåëåííî çàïîìèíàþò â D 2 ýëåìåíòàõ ïàìÿòè. Âðåìÿ âûïîëíåíèÿ çàïðîñà òàêæå ïðîïîðöèîíàëüíî D 2 . Ïîý- òîìó, åñëè çàïîìíèòü â NAM N D�� âåêòîðîâ ñ âîçìîæíîñòüþ âîññòàíîâëåíèÿ, ïîÿâëÿþòñÿ ïðåäïîñûëêè ñóáëèíåéíîãî ïîèñêà. Òàêîå çàïîìèíàíèå äîñòèæèìî äëÿ ñëó÷àéíûõ ðàçðåæåííûõ áèíàðíûõ âåêòîðîâ áîëüøîé ðàçìåðíîñòè. Íåîáõî- äèìû äàëüíåéøèå èññëåäîâàíèÿ âîçìîæíîñòè óñêîðåíèÿ ïîèñêà äëÿ íåêîòîðûõ NAM ïî ñðàâíåíèþ ñ äðóãèìè ÈÑ äëÿ ðàçðåæåííûõ áèíàðíûõ âåêòîðîâ. Ïåð- ñïåêòèâíûì íàïðàâëåíèåì ÿâëÿåòñÿ èñïîëüçîâàíèå íåïîëíîñâÿçíûõ ñåòåé, ÷òî ñíèæàåò çàòðàòû ïàìÿòè è âðåìÿ ïîèñêà äî ëèíåéíîãî îò ðàçìåðíîñòè. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 187 Äëÿ ðÿäà NAM ëó÷øèå õàðàêòåðèñòèêè äîñòèãàþòñÿ ïðè D � �, ÷òî îòëè÷- íî îò ïîâåäåíèÿ ÈÑ, îïèñàííûõ â ðàçä. 2–5. Âñëåäñòâèå ýòèõ ðàçëè÷èé ïåðñïåê- òèâíî èññëåäîâàíèå ñîâìåñòíîãî èñïîëüçîâàíèÿ NAM ñ äðóãèìè ÈÑ. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Manning C., Raghavan P., Sch��utze H. Introduction to information retrieval. New York: Cambridge Uni- versity Press, 2008. 506 p. 2. Datta R., Joshi D., Li J., Wang J. Image retrieval: Ideas, influences, and trends of the new age. ACM Com- puting Surveys. 2008. Vol. 40, N 2. P. 1–60. 3. Fouad Ì.Ì. Content-based search for image retrieval. I.J. Image, Graphics and Signal Processing. 2013. Vol. 5, N 11. P. 46–52. 4. Rachkovkij D.A. Distance-based index structures for fast similarity search. Cybernetics and Systems Analy- sis. 2017. Vol. 53, N 4. P. 636–658. 5. Heinly J., Dunn E., Frahm J.-M. Comparative evaluation of binary features. Proc. ECCV’12. 2012. P. 759–773. 6. Khalifa F.A., Semary N.A., El-Sayed H.M., Hadhoud M.M. Local detectors and descriptors for object class recognition. International Journal of Intelligent Systems and Applications. 2015. Vol. 7, N 10. P. 12–18. 7. Uchida Y. Local feature detectors, descriptors, and image representations: A survey. arXiv:1607.08368. 28 Jul 2016. 8. Rastegari M., Ordonez V., Redmon J., Farhadi A. Xnor-net: Imagenet classification using binary convolutional neural networks. Proc. ECCV’16. 2016. P. 525–542. 9. Hubara I., Courbariaux M., Soudry D., El-Yaniv R., Bengio Y. Binarized neural networks. Proc. NIPS’16. 2016. P. 4107–4115. 10. Tang W., Hua G., Wang L. How to train a compact binary neural network with high accuracy? Proc. AAAI’17. 2017. P. 2625–2631. 11. Kumar S., Desai J.V., Mukherjee S. Copy move forgery detection in contrast variant environment using binary DCT vectors. I.J. Image, Graphics and Signal Processing. 2015. Vol. 7, N 6. P. 38–44. 12. Faruqui M., Dyer C. Non-distributional word vector representations. Proc. ACL-IJCNLP’15. 2015. Vol. 2. P. 464–469. 13. Ren S., Cao X., Wei Y., Sun J. Face alignment at 3000 fps via regressing local binary features. Proc. CVPR’14. 2014. P. 1685–1692. 14. Pavlov D.N., Mannila H., Smyth P. Beyond independence: probabilistic models for query approximation on binary transaction data. IEEE TKDE. 2003. Vol. 15, N 6. P. 1409–1421. 15. Wang J., Shen H.T., Song J., Ji J. Hashing for similarity search: A survey. arXiv:1408.2927. 13 Aug 2014. 16. Rachkovskij D.A., Kussul E.M., Baidyk T.N. Building a world model with structure-sensitive sparse bi- nary distributed representations. BICA. 2013. Vol. 3. P. 64–86. 17. Rachkovskij D.A. Binary vectors for fast distance and similarity estimation. Cybernetics and Systems Analysis. 2017. Vol. 53, N 1. P. 138–156. 18. Wang J., Liu W., Kumar S., Chang S.-F. Learning to hash for indexing big data: A survey. Proceedings of the IEEE. 2016. Vol. 104, N 1. P. 34–57. 19. 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 20. Rachkovskij D.A. Real-valued vectors for fast distance and similarity estimation. Cybernetics and Systems Analysis. 2016. Vol. 52, N 6. P. 967–988. 21. Gaede V., Gunther O. Multidimensional access methods. ACM Comput. Surv. 1998. Vol. 30, N 2. P. 170–231. 22. Bohm Ñ., Berchtold S., Keim D.A. Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databas. ACM Comp. Surv. 2001. Vol. 33, N 3. P. 322–373. 23. Samet H. Foundations of multidimensional and metric data structures. San Francisco: Morgan Kaufmann, 2006. 1024 p. 24. Haque I.S., Pande V.S., Walters W.P. Anatomy of high-performance 2d similarity calculations. Journal of Chemical Information and Modeling. 2011. Vol. 51, N 9. P. 2345–2351. 25. Donaldson R., Gupta A, Plan Y., Reimer T. Random mappings designed for commercial search engines. arXiv:1507.05929. 21 Jul 2015. 26. Brodal G., Gasieniec L. Approximate dictionary queries. Proc. CPM’96. 1996. P. 65–74. 27. Carter. L., Wegman M.N. Universal classes of hash functions. Journal of Computer and System Sciences. 1979. Vol. 18, N 2. P. 143–154. 28. Fredman M.L., Komlos J., Szemeredi E. Storing a sparse table with O(1) worst case access time. Journal of the ACM. 1984. Vol. 31, N 3. P. 538–544. 188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 29. Chegrane I., Belazzougui D. Simple, compact and robust approximate string dictionary. J. Discrete Algo- rithms. 2014. Vol. 28. P. 49–60. 30. Pagh R. Locality-sensitive hashing without false negatives. Proc. SODA’16. 2016. P. 1–9. 31. Andoni A., Indyk P. Nearest neighbors in high-dimensional spaces. In: Handbook of Discrete and Compu- tational Geometry, 3rd edition. 2017. Chap. 43. P. 1133–1153. 32. Zobel J., Moffat A. Inverted files for text search engines. ACM Comput. Surv. 2006. Vol. 38, N 2. P. 6:1–6:56. 33. Rachkovskij D.A., Slipchenko S.V. Similarity-based retrieval with structure-sensitive sparse binary dis- tributed representations. Computational Intelligence. 2012. Vol. 28, N 1. P. 106–129. 34. Ferdowsi S., Voloshynovskiy S., Kostadinov D., Holotyak T. Fast content identification in high- dimensional feature spaces using sparse ternary codes. Proc. WIFS’16. 2016. P. 1–6. 35. 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. 36. Tatti N., Mielikainen T., Gionis A., Mannila H. What is the dimension of your binary data? Proc. ICDM’06. 2006. P. 603–612. 37. Alman J., Williams R. Probabilistic polynomials and hamming nearest neighbors. Proc. FOCS’15. 2015. P.136–150. 38. Powers D.M.W. Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and correlation. Journal of Machine Learning Tech. 2011. Vol. 2, N 1. P. 37–63. 39. Muja M., Lowe D.G. Scalable nearest neighbor algorithms for high dimensional data. IEEE TPAMI. 2014. Vol. 36, N 11. P. 2227–2240. 40. Yao A.C., Yao F.F. Dictionary look-up with one error. Journal of Algorithms. 1997. Vol. 25, N 1. P. 194–202. 41. Brodal G. S., Srinivasan V. Improved bounds for dictionary look-up with one error. Information Process- ing Letters. 2000. Vol. 75, N 1–2. P. 57–59. 42. Cole R., Gottlieb L.-A., Lewenstein M. Dictionary matching and indexing with errors and don’t cares. Proc. STOC’04. 2004. P. 91–100. 43. Chan H.-L., Lam T.-W., Sung W.-K., Tam S.-L., Wong S.-S. A linear size index for approximate pattern matching. Journal of Discrete Algorithms. 2011. Vol. 9, N 4. P. 358–364. 44. Chan H., Lam T. W., Sung W., Tam S., Wong S. Compressed indexes for approximate string matching. Algorithmica. 2010. Vol. 58, N 2. P. 263–281. 45. Greene D., Parnas M., Yao F. Multi-index hashing for information retrieval. Proc. FOCS’94. 1994. P. 722–731. 46. Wu S., Manber U. Fast text searching allowing errors. Communications of the ACM. Vol. 35, N 10. 1992. P. 83–91. 47. Manku G.S., Jain A., Sarma A.D. Detecting near-duplicates for web crawling. Proc. WWW’07. 2007. P. 141–150. 48. Liu A.X., Ke S., Torng E. Large scale hamming distance query processing. Proc. ICDE’11. 2011. P. 553–564. 49. Gog S., Venturini R. Fast and compact Hamming distance index. Proc. SIGIR’16. 2016. P. 285–294. 50. Zhang X., Qin J., Wang W., Sun Y., Lu J. Hmsearch: An efficient hamming distance query processing al- gorithm. Proc. SSDBM’13. 2013. P. 19:1–19:12. 51. 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. 52. Wan J., Tang S., Zhang Y., Huang L., Li J. Data driven multi-index hashing. Proc. ICIP’13. 2013. P. 2670–2673. 53. Ma Y., Zou H., Xie H., Su Q. Fast search with data-oriented multi-index hashing for multimedia data. KSII TIIS. 2015. Vol. 9, N 7. P. 2599–2613. 54. Wang M., Feng X., Cui J. Multi-index hashing with repeat-bits in hamming space. Proc. FSKD’15. 2015. P. 1307–1313. 55. Song J., Shen H.T., Wang J., Huang Z., Sebe N., Wang J. A distance-computation-free search scheme for binary code databases. IEEE Trans. Multimedia. 2016. Vol. 18, N 3. P. 484–495. 56. Ong E.-J., Bober M. Improved Hamming distance search using variable length hashing. Proc. CVPR’16. 2016. P. 2000–2008. 57. Eghbali S., Tahvildari L. Cosine similarity search with multi-index hashing. arXiv:1610.00574. 14 Sep 2016. 58. Andoni A., Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimen- sions. Communications of the ACM. 2008. Vol. 51. N 1. P. 117–122. 59. Har-Peled S., Indyk P., Motwani R. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory Comput. 2012. Vol. 8. P. 321–350. 60. Shrivastava A., Li P. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). Proc. NIPS’14. 2014. P. 2321–2329. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 189 61. Charikar M. Similarity estimation techniques from rounding algorithms. Proc. STOC’02. 2002. P. 380–388. 62. Shrivastava A., Li P. Asymmetric minwise hashing for indexing binary inner products and set contain- ment. Proc. WWW’15. 2015. P. 981–991. 63. Andoni A., Datar M., Immorlica N., Indyk P., Mirrokni V. S. Locality-sensitive hashing using stable distri- butions. P. 61–72. In: Nearest Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, Cambridge. 2006. 280 p. 64. 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. 65. Broder A.Z. On the resemblance and containment of documents. Proc. SEQUENCES’97. 1997. P. 21–29. 66. Broder A.Z., Glassman S.C., Manasse M. S., Zweig G. Syntactic clustering of the web. Computer Net- works and ISDN Systems. 1997. Vol. 29, N 8–13. P. 1157–1166. 67. Broder A.Z., Charikar M., Frieze A.M., Mitzenmacher M. Min-wise independent permutations. J. Comput. System Sci. 1998. Vol. 60. P. 327–336. 68. Tang J., Tian Y. A systematic review on minwise hashing algorithms. Annals of Data Science. 2016. Vol. 3, N 4. P. 445–468. 69. Dahlgaard S., Knudsen M.B.T, Thorup M. Fast similarity sketching. arXiv:1704.04370. 14 Apr 2017. 70. Li P., K��înig A.C. Theory and applications of b-bit minwise hashing. Communications of the ACM. 2011. Vol. 54, N 8. P. 101–109. 71. Shrivastava A. Optimal densification for fast and accurate minwise hashing. arXiv:1703.04664. 14 Mar 2017. 72. Shrivastava A., Li P. In defense of minhash over simhash. Proc. AISTATS’14. 2014. P. 886–894. 73. Ahle T.D., Pagh R., Razenshteyn I., Silvestri F. On the complexity of inner product similarity join. Proc. PODS’16. 2016. P. 151–164. 74. Bera D., Pratap R.. Frequent-itemset mining using locality-sensitive hashing. Proc. COCOON’16. 2016. P. 143–155. 75. Trzcinski T., Lepetit V., Fua P. Thick boundaries in binary space and their influence on nearest-neighbor search. Pattern Recognition Letters. 2012. Vol. 33, N 16. P. 2173–2180. 76. Esmaeili M.M., Ward R.K., Fatourechi M. A fast approximate nearest neighbor search algorithm in the Hamming space. IEEE Trans. PAMI. 2012. Vol. 34, N 12. P. 2481–2488. 77. Har-Peled S., Mahabadi S. Proximity in the age of distraction: Robust approximate nearest neighbor search. Proc. SODA’17. 2017. P. 1–15. 78. Ahle T.D., Aumuller M., Pagh R. Parameter-free locality sensitive hashing for spherical range reporting. Proc. SODA’17. 2017. P. 239–256. 79. Pham N. Hybrid LSH: Faster near neighbors reporting in high-dimensional space. Proc. EDBT’17. 2017. P. 454–457. 80. Flajolet P., Fusy E., Gandouet O., Meunier F. Hyperloglog: The analysis of a near-optimal cardinality esti- mation algorithm. Proc. AofA’07. 2007. P. 127–146. 81. Pham N., Pagh R. Scalability and total recall with fast ÑoveringLSH. Proc. CIKM’16. 2016. P. 1109–1118. 82. Becker A., Ducas L., Gama N., Laarhoven T. New directions in nearest neighbor searching with applica- tions to lattice sieving. Proc. SODA’16. 2016. P. 10–24. 83. 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. 84. Christiani T., Pagh R. Set similarity search beyond MinHash. Proc. STOC’17. 2017. P. 1094–1107. 85. Ahle T.D. Optimal Las Vegas locality sensitive data structures. arXiv:1704.02054. April 6 2017. 86. Andoni A., Razenshteyn I. Optimal data-dependent hashing for approximate near neighbors. Proc. STOC’15. 2015. P. 793–801. 87. Andoni A., Razenshteyn I., Shekel Nosatzki N. Lsh forest: Practical algorithms made theoretical. Proc. SODA’17. 2017. P. 67–78. 88. Bawa M., Condie T., Ganesan P. Lsh forest: self-tuning indexes for similarity search. Proc. WWW’05. 2005. P. 651–660. 89. Qian G., Zhu Q., Xue Q., Pramanik S. Dynamic indexing for multidimensional non-ordered discrete data spaces using a data-partitioning approach. ACM TODS. 2006. Vol. 31, N 2. P. 439–484. 90. Qian G., Zhu Q., Xue Q., Pramanik S. A space-partitioning-based indexing method for multidimensional non-ordered discrete data spaces. ACM TOIS. 2006. Vol. 23. P. 79–110. 91. Yan C.C., Xie H., Zhang B., Ma Y., Dai Q., Liu Y. Fast approximate matching of binary codes with dis- tinctive bits. Front. Comput. Sci. 2015. Vol. 9, N 5. P. 741–750. 92. Galvez-Lopez D., Tardos J.D. Bags of binary words for fast place recognition in image sequences. IEEE Trans. Robotics. 2012. Vol. 28, N 5. P. 1188–1197. 93. Luo Q., Zhang S., Huang T., Gao W., Tian Q. Scalable mobile search with binary phrase. Proc. ICIMCS’13. 2013. P. 66–70. 94. Niedermayer J., Kroger P. Retrieval of binary features in image databases: A study. Proc. SISAP’14. 2014. P. 151–163. 190 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 95. Kryzhanovsky V., Malsagov M., Tomas J.A.C., Zhelavskaya I. On error probability of search in high-di- mensional binary space with scalar neural network tree. Proc. NCTA’14. 2014. 96. Tang M., Yu Y., Aref W.G., Malluhi Q.M., Ouzzani M. Efficient processing of hamming-distance-based similarity-search queries over mapreduce. Proc. EDBT’15. 2015. P. 361–372. 97. Tao Y., Yi K., Sheng C., Kalnis P. Efficient and accurate nearest neighbor and closest pair search in high-dimensional space. ACM Trans. Database Syst. 2010. Vol. 35, N 3. P. 20:1–20:46. 98. Jiang Z., Xie L., Deng X., Xu W., Wang J. Fast nearest neighbor search in the hamming space. Proc. MMM’16. 2016. P. 325–336. 99. Malkov Yu. A., Yashunin D. A. Efficient and robust approximate nearest neighbor search using Hierar- chical Navigable Small World graphs. arXiv:1603.09320. 21 May 2016. 100. 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. 101. Valiant L.G. Functionality in neural nets. Proc. AAAI’88. 1988. Vol. 2. P. 629–634. 102. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities. Proc. of the Nat. Acad. Sci. USA. 1982. Vol. 79, N 8. P. 2554–2558. 103. Tsodyks M., Feigelman M. The enhanced storage capacity in neural networks with low activity level. Europhysics Letters. 1988. Vol. 6, N 2. P. 101–105. 104. Frolov A.A., Husek D., Muraviev I.P. Information capacity and recall quality in sparsely encoded Hopfield-like neural network: Analytical approaches and computer simulation. Neural Networks. 1997. Vol. 10, N 5. P. 845–855. 105. Frolov A.A., Husek D., Muraviev I.P. Informational efficiency of sparsely encoded Hopfield-like associa- tive memory. Optical Memory & Neural Networks. 2003. Vol. 12, N 3. P. 177–197. 106. Amari S. Characteristics of sparsely encoded associative memory. Neural Networks. 1989. Vol. 2, N 6. P. 451–457. 107. Heusel J., Lowe M., Vermet F. On the capacity of an associative memory model based on neural cliques. Statist. Probab. Lett. 2015. Vol. 106. P. 256–261. 108. Gripon V., Heusel J., Lowe M., Vermet F. A comparative study of sparse associative memories. Journal of Statistical Physics. 2016. Vol. 164. P. 105–129. 109. Frolov A.A., Husek D., Rachkovskij D.A. Time of searching for similar binary vectors in associative memory. Cybernetics and Systems Analysis. 2006. Vol. 42, N 5. P. 615–623. 110. Palm G. On associative memory. Biological Cybernetics. 1980. Vol. 36. P. 19–31. 111. Tsodyks M.V. Associative memory in neural networks with binary synapses. Mod. Phys. Lett. 1990. Vol. B4. P. 713–716. 112. Frolov A., Kartashov A., Goltsev A., Folk R. Quality and efficiency of retrieval for Willshaw-like autoassociative networks. Correction. Network. 1995. Vol. 6. P. 513–534. 113. Schwenker F., Sommer F.T., Palm G. Iterative retrieval of sparsely coded associative memory patterns. Neural Networks. 1996. Vol. 9. P. 445-455. 114. Frolov A.A., Rachkovskij D.A., Husek D. On information characteristics of Willshaw-like auto-associa- tive memory. Neural Network World. 2002. Vol. 12, N 2. P. 141–157. 115. Kanter I. Potts-glass models of neural networks. Physical Rev. A. 1988. V. 37, N 7. P. 2739–2742. 116. Lowe M., Vermet F. The capacity of q-state Potts neural networks with parallel retrieval dynamics. Statis- tics and Probability Letters. 2007. Vol. 77, N 4. P. 1505–1514. 117. Onizawa N., Jarollahi H., Hanyu T., Gross W.J. Hardware implementation of associative memories based on multiple-valued sparse clustered networks. IEEE Journal on Emerging and Selected Topics in Circuits and Systems. 2016. Vol. 6, N 1. P. 13–24. 118. Kartashov A., Frolov A., Goltsev A., Folk R. Quality and efficiency of retrieval for Willshaw-like autoassociative networks. Willshaw–Potts model. Network. 1997. Vol. 8, N 1. P. 71–86. 119. Gripon V., Berrou C. Sparse neural networks with large learning diversity. IEEE Trans. on Neural Net- works. 2011. Vol. 22, N 7. P. 1087–1096. 120. Tsodyks M. Associative memory in asymmetric diluted network with low level of activity. Europhysics Letters. 1988. Vol. 7, N 3. 203–208. 121. Buckingham J., Willshaw D. On setting unit thresholds in an incompletely connected associative net. Net- work. 1993. Vol. 4. P. 441–459. 122. Yu C., Gripon V., Jiang X., Jegou H. Neural associative memories as accelerators for binary vector search. Proc. COGNITIVE’15. 2015. P. 85–89. 123. Frolov A.A., Husek D., Muraviev I.P., Polyakov P. Boolean factor analysis by attractor neural network. IEEE Trans. Neural Networks. 2007. Vol. 18, N 3. P. 698–707. 124. Peretto P., Niez J.J. Long term memory storage capacity of multiconnected neural networks. Biol. Cybern. 1986. Vol. 54, N 1. P. 53–63. 125. Baldi P., Venkatesh S.S. Number of stable points for spin-glasses and neural networks of higher orders. Physical Review Letters. 1987. Vol. 58, N 9. P. 913–916. 126. Krotov D., Hopfield J.J. Dense associative memory for pattern recognition. Proc. NIPS’16. 2016. P. 1172–1180. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5 191 127. Krotov D., Hopfield J. Dense associative memory is robust to adversarial inputs. arXiv:1701.00939. 4 Jan 2017. 128. Demircigil M., Heusel J., Lowe M., Upgang S., Vermet F. On a model of associative memory with huge storage capacity. Journal Stat. Phys. 2017. Vol. 168, N 2. P. 288–299. 129. Karbasi A., Salavati A. H., Shokrollahi A. Iterative learning and denoising in convolutional neural asso- ciative memories. Proc. ICML’13. 2013. P. 445–453. 130. Salavati A.H., Kumar K.R., Shokrollahi A. Nonbinary associative memory with exponential pattern re- trieval capacity and iterative learning. IEEE Trans. Neural Networks and Learning Systems. 2014. Vol. 25, N 3. P. 557–570. 131. Mazumdar A., Rawat A.S. Associative memory via a sparse recovery model. Proc. NIPS’15. 2015. P. 2683–2691. 132. Mazumdar A., Rawat A.S. Associative memory using dictionary learning and expander decoding. Proc. AAAI’17. 2017. P. 267–273. 133. Mansor M.A., Kasihmuddin M.S.M., Sathasivam S. VLSI circuit configuration using satisfiability logic in Hopfield network. International Journal of Intelligent Systems and Applications (IJISA). 2016. Vol. 8, N 9. P. 22–29. 134. Mansor M.A., Kasihmuddin M.S.M., Sathasivam S. Enhanced hopfield network for pattern satisfiability optimization. International Journal of Intelligent Systems and Applications (IJISA). 2016. Vol. 8, N 11. P. 27–33. Íàä³éøëà äî ðåäàêö³¿ 07.02.2017 Ä.À. Ðà÷êîâñüêèé ²ÍÄÅÊÑÍ² ÑÒÐÓÊÒÓÐÈ ÄËß ØÂÈÄÊÎÃÎ ÏÎØÓÊÓ ÇÀ ÑÕÎÆ²ÑÒÞ Á²ÍÀÐÍÈÕ ÂÅÊÒÎÐ²Â Àíîòàö³ÿ. Íàâåäåíî îãëÿä ³íäåêñíèõ ñòðóêòóð äëÿ øâèäêîãî ïîøóêó çà ñõîæ³ñòþ îá’ºêò³â, ùî ïðåäñòàâëåí³ á³íàðíèìè âåêòîðàìè (³ç êîìïîíåíòàìè 0 àáî 1). Ðîçãëÿíóòî ñòðóêòóðè ÿê äëÿ òî÷íîãî, òàê ³ äëÿ íàáëèæåíîãî ïî- øóêó çà â³äñòàííþ Õåìì³íãà òà ³íøèìè ì³ðàìè ñõîæîñò³. Îïèñàíî, ãîëîâ- íèì ÷èíîì, ³íäåêñí³ ñòðóêòóðè íà îñíîâ³ õåø-òàáëèöü, õåøóâàííÿ, ùî çáåð³ãàº ñõîæ³ñòü, à òàêîæ äåðåâîâèäíèõ ñòðóêòóð, ãðàô³â ñóñ³äñòâà òà íåé- ðîìåðåæåâî¿ ðîçïîä³ëåíî¿ àâòîàñîö³àòèâíî¿ ïàì’ÿò³. Âèêëàäåíî ³äå¿ êîíêðåò- íèõ àëãîðèòì³â (â³äîìèõ òà íåùîäàâíî çàïðîïîíîâàíèõ). Êëþ÷îâ³ ñëîâà: ïîøóê çà ñõîæ³ñòþ, â³äñòàíü Õåìì³íãà, íàéáëèæ÷èé ñóñ³ä, áëèæí³é ñóñ³ä, ³íäåêñí³ ñòðóêòóðè, ìóëüòè³íäåêñíå õåøóâàííÿ, ëîêàëü- íî-÷óòëèâå õåøóâàííÿ, äåðåâîâèäí³ ñòðóêòóðè, ãðàô ñóñ³äñòâà, íåéðîìåðå- æåâà àâòîàñîö³àòèâíà ïàì’ÿòü. D.A. Rachkovskij INDEX STRUCTURES FOR FAST SIMILARITY SEARCH OF BINARY VECTORS Abstract. We survey index structures for fast similarity search of objects represented by binary vectors (with components 0 or 1). Structures for both exact and approximate search by Hamming distance and other similarity measures are considered. Mainly, we present index structures based on hash tables, similarity-preserving hashing, as well as tree structures, neighborhood graphs, and neural distributed autoassociative memory. The ideas of specific algorithms, including the recently proposed ones, are outlined. Keywords: similarity search, Hamming distance, nearest neighbor, near neighbor, index structures, multi-index hashing, locally-sensitive hashing, treelike structures, neighborhood graph, neural autoassociative memory. Ðà÷êîâñêèé Äìèòðèé Àíäðååâè÷, äîêòîð òåõí. íàóê, âåäóùèé íàó÷íûé ñîòðóäíèê Ìåæäóíàðîäíîãî íàó÷íî-ó÷åáíîãî öåíòðà èíôîð- ìàöèîííûõ òåõíîëîãèé è ñèñòåì ÍÀÍ Óêðàèíû è ÌÎÍ Óêðàèíû, Êèåâ, e-mail: dar@infrm.kiev.ua. 192 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 5

Индексные структуры для быстрого поиска по сходству бинарных векторов

Institution

Ähnliche Einträge