Основанные на расстояниях индексные структуры для быстрого поиска по сходству
Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2017
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/144783 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144783 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1447832025-02-09T13:40:36Z Основанные на расстояниях индексные структуры для быстрого поиска по сходству Основані на відстанях індексні структури для швидкого пошуку за схожістю Distance-based index structures for fast similarity search Рачковский, Д.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство треугольника и другие метрические аксиомы), так и по неметрическим. Представлены структуры, которые возвращают объекты базы, являющиеся точным ответом на поисковый запрос, а также структуры для приближенного поиска по сходству (они не гарантируют точность, но обычно возвращают близкие к точным результаты и работают быстрее структур для точного поиска). Изложены общие принципы конструирования и применения некоторых индексных структур, а также рассмотрены идеи, лежащие в основе конкретных алгоритмов, как известных, так и предложенных в последнее время. Розглянуто клас таких індексних структур для швидкого пошуку за схожістю, при конструюванні та застосуванні яких використовують тільки інформацію про значення або ранг деяких відстаней/схожостей між об’єктами. Обговорено пошук як за метричними відстанями (для яких виконується нерівність трикутника та інші метричні аксіоми), так і за неметричними. Наведено структури, які повертають об’єкти бази, що є точною відповіддю на запит, а також структури для наближеного пошуку за схожістю (вони не гарантують точності, але зазвичай повертають близькі до точних результати та працюють швидше структур для точного пошуку). Викладено загальні принципи конструювання і застосування деяких індексних структур, а також розглянуто ідеї, на яких базуються конкретні алгоритми (відомі та запропоновані останнім часом). In this survey paper we consider the class of index structures for fast similarity search that uses for index construction and application only information about the values or ranks of some distances/similarities between objects. We discuss the search by metric distances (for which the triangle inequality and other metric axioms are valid), as well as by non-metric ones. Considered index structures include those returning the objects of the base that are exact results to the similarity search query, and index structures for approximate similarity search, which do not guarantee the accuracy, but usually return close to accurate results and work faster than the structures for exact search. Some general principles for construction and usage of index structures as well as some ideas of specific algorithms, including recently proposed ones, are discussed. 2017 Article Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/144783 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 |
Рассмотрен класс таких индексных структур для быстрого поиска по сходству, при конструировании и применении которых используется только информация о значениях или ранге некоторых расстояний/сходств между объектами. Обсужден поиск как по метрическим расстояниям (для последних выполняется неравенство треугольника и другие метрические аксиомы), так и по неметрическим. Представлены структуры, которые возвращают объекты базы, являющиеся точным ответом на поисковый запрос, а также структуры для приближенного поиска по сходству (они не гарантируют точность, но обычно возвращают близкие к точным результаты и работают быстрее структур для точного поиска). Изложены общие принципы конструирования и применения некоторых индексных структур, а также рассмотрены идеи, лежащие в основе конкретных алгоритмов, как известных, так и предложенных в последнее время. |
| 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/144783 |
| citation_txt |
Основанные на расстояниях индексные структуры для быстрого поиска по сходству / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 165–192. — Бібліогр.: 148 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT račkovskijda osnovannyenarasstoâniâhindeksnyestrukturydlâbystrogopoiskaposhodstvu AT račkovskijda osnovanínavídstanâhíndeksnístrukturidlâšvidkogopošukuzashožístû AT račkovskijda distancebasedindexstructuresforfastsimilaritysearch |
| first_indexed |
2025-11-26T08:26:29Z |
| last_indexed |
2025-11-26T08:26:29Z |
| _version_ |
1849840738827763712 |
| fulltext |
ÓÄÊ 004.22 + 004.93'11
Ä.À. ÐÀ×ÊÎÂÑÊÈÉ
ÎÑÍÎÂÀÍÍÛÅ ÍÀ ÐÀÑÑÒÎßÍÈßÕ ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ
ÄËß ÁÛÑÒÐÎÃÎ ÏÎÈÑÊÀ ÏÎ ÑÕÎÄÑÒÂÓ
Àííîòàöèÿ. Ðàññìîòðåí êëàññ òàêèõ èíäåêñíûõ ñòðóêòóð äëÿ áûñòðîãî ïî-
èñêà ïî ñõîäñòâó, ïðè êîíñòðóèðîâàíèè è ïðèìåíåíèè êîòîðûõ èñïîëüçóåò-
ñÿ òîëüêî èíôîðìàöèÿ î çíà÷åíèÿõ èëè ðàíãå íåêîòîðûõ ðàññòîÿíèé/ñõîäñòâ
ìåæäó îáúåêòàìè. Îáñóæäåí ïîèñê êàê ïî ìåòðè÷åñêèì ðàññòîÿíèÿì (äëÿ
ïîñëåäíèõ âûïîëíÿåòñÿ íåðàâåíñòâî òðåóãîëüíèêà è äðóãèå ìåòðè÷åñêèå àê-
ñèîìû), òàê è ïî íåìåòðè÷åñêèì. Ïðåäñòàâëåíû ñòðóêòóðû, êîòîðûå âîçâðà-
ùàþò îáúåêòû áàçû, ÿâëÿþùèåñÿ òî÷íûì îòâåòîì íà ïîèñêîâûé çàïðîñ,
à òàêæå ñòðóêòóðû äëÿ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó (îíè íå ãàðàíòè-
ðóþò òî÷íîñòü, íî îáû÷íî âîçâðàùàþò áëèçêèå ê òî÷íûì ðåçóëüòàòû è ðà-
áîòàþò áûñòðåå ñòðóêòóð äëÿ òî÷íîãî ïîèñêà). Èçëîæåíû îáùèå ïðèíöèïû
êîíñòðóèðîâàíèÿ è ïðèìåíåíèÿ íåêîòîðûõ èíäåêñíûõ ñòðóêòóð, à òàêæå
ðàññìîòðåíû èäåè, ëåæàùèå â îñíîâå êîíêðåòíûõ àëãîðèòìîâ, êàê èçâåñò-
íûõ, òàê è ïðåäëîæåííûõ â ïîñëåäíåå âðåìÿ.
Êëþ÷åâûå ñëîâà: ïîèñê ïî ñõîäñòâó, ïîèñê áëèæàéøåãî ñîñåäà, èíäåêñíûå
ñòðóêòóðû, èíäåêñèðîâàíèå íà îñíîâå ðàññòîÿíèé, ìåòðè÷åñêîå ðàññòîÿíèå,
íåìåòðè÷åñêîå ðàññòîÿíèå, ìåòðè÷åñêîå äåðåâî, ãðàô ñîñåäñòâà, ìåòîä âåò-
âåé è ãðàíèö.
ÂÂÅÄÅÍÈÅ
Çà÷àñòóþ åäèíñòâåííûì ñïîñîáîì íàéòè íóæíóþ èíôîðìàöèþ (îáúåêòû) â áîëü-
øèõ ìàññèâàõ äàííûõ ÿâëÿåòñÿ îïðåäåëåíèå åå ñõîäñòâà ñ óæå èìåþùèìèñÿ ïðè-
ìåðàìè òàêîé èíôîðìàöèè. Ïîñëåäíèå èñïîëüçóþòñÿ â êà÷åñòâå çàïðîñîâ ê áàçå
(íàáîðó, ìàññèâó, ìíîæåñòâó) îáúåêòîâ. Âåëè÷èíà ñõîäñòâà ÿâëÿåòñÿ êðèòåðèåì
óïîðÿäî÷èâàíèÿ îáúåêòîâ áàçû îòíîñèòåëüíî îáúåêòà-çàïðîñà (íå ïðèíàäëåæàùå-
ãî áàçå). Òàêèì îáðàçîì, ïîèñê ïî ñõîäñòâó — ýòî âàðèàíò èíôîðìàöèîííîãî ïî-
èñêà, ïðè êîòîðîì îáúåêòû áàçû, ðåëåâàíòíûå îáúåêòó-çàïðîñó, îïðåäåëÿþòñÿ íà
îñíîâå ÷èñëîâûõ çíà÷åíèé íåêîòîðûõ ìåð (ôóíêöèé) ñõîäñòâà èëè íåñõîäñòâà
(ðàññòîÿíèÿ) ìåæäó ïðåäñòàâëåíèÿìè îáúåêòîâ.
Ïîëó÷åííûå ïîèñêîì ïî ñõîäñòâó äàííûå ìîæíî èñïîëüçîâàòü íåïîñðåä-
ñòâåííî èëè â êà÷åñòâå èñòî÷íèêà äîïîëíèòåëüíîé èíôîðìàöèè î âõîäíîì îáúåê-
òå-çàïðîñå. Òàê, åñëè íàéäåííûå èçîáðàæåíèÿ èëè òåêñòû óäîâëåòâîðÿþò èíôîð-
ìàöèîííóþ ïîòðåáíîñòü ïîëüçîâàòåëÿ, îíè ìîãóò áûòü êîíå÷íûì ðåçóëüòàòîì ïî-
èñêà [1, 2]. Åñëè ïîñòàâëåíà çàäà÷à îïðåäåëèòü ïðèíàäëåæíîñòü îáúåêòà-çàïðîñà
ê íåêîòîðîìó êëàññó, äëÿ åå ðåøåíèÿ ìîæíî ïðèìåíèòü ìåòîä êëàññèôèêàöèè áëè-
æàéøåãî ñîñåäà, ïðèñâàèâàþùèé îáúåêòó-çàïðîñó òîò êëàññ, ê êîòîðîìó ïðèíàä-
ëåæàò ñõîäíûå ñ íèì îáúåêòû [3]. Ýòî ïðîñòîé âàðèàíò ïîäõîäà «ðàññóæäåíèÿ íà
îñíîâå ïðèìåðîâ» (example based reasoning), ê åãî ðàçíîâèäíîñòÿì îòíîñÿòñÿ ðàñ-
ñóæäåíèÿ ïî ïðåöåäåíòàì (case-based reasoning) è ïî àíàëîãèè (analogical
reasoning), ñì. [4–9] è ññûëêè ê íèì. Ïîäõîä èñïîëüçóåò ñõîäíûå ïðåöåäåíòû èëè
àíàëîãè äëÿ âûâîäîâ î âõîäíîì îáúåêòå èëè ñèòóàöèè è ïðèìåíÿåòñÿ êàê ëþäüìè,
òàê è òåõíè÷åñêèìè ñèñòåìàìè äëÿ ðåøåíèÿ øèðîêîãî êðóãà çàäà÷.
Ïðàêòè÷åñêàÿ ïîëåçíîñòü àëãîðèòìîâ ïîèñêà ïî ñõîäñòâó îïðåäåëÿåòñÿ ñêî-
ðîñòüþ ïîèñêà è çàòðàòàìè ïàìÿòè, à òàêæå ñîîòâåòñòâèåì ðåçóëüòàòîâ ïîèñêà
ïîòðåáíîñòÿì ïîëüçîâàòåëÿ. Ïîñëåäíåå çàâèñèò, â ÷àñòíîñòè, îò èñïîëüçóåìûõ
ïðåäñòàâëåíèé îáúåêòîâ è ìåð ðàññòîÿíèÿ/ñõîäñòâà, áàçû è îáúåêòîâ-çàïðîñîâ.
Áóäåì ñ÷èòàòü èõ çàäàííûìè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 165
© Ä.À. Ðà÷êîâñêèé, 2017
Ïðîùå âñåãî âûïîëíèòü ïîèñê ïî ñõîäñòâó âû÷èñëåíèåì âåëè÷èí ñõîäñòâ îáú-
åêòà-çàïðîñà ñî âñåìè îáúåêòàìè áàçû è âîçâðàùåíèåì îáúåêòîâ, óäîâëåòâîðÿþùèõ
óñëîâèÿì çàïðîñà. Òàêîé ëèíåéíûé èëè ïîñëåäîâàòåëüíûé ïîèñê ÷àñòî îêàçûâàåòñÿ
íåäîïóñòèìî ìåäëåííûì, îñîáåííî äëÿ áîëüøèõ áàç, ñëîæíûõ ìíîãîêîìïîíåíòíûõ
ïðåäñòàâëåíèé îáúåêòîâ è âû÷èñëèòåëüíî ñëîæíûõ ìåð ñõîäñòâà.
Îäèí ïîäõîä ê óñêîðåíèþ ëèíåéíîãî ïîèñêà ïî ñõîäñòâó ñîñòîèò â áûñòðîé
(õîòÿ è ïðèáëèæåííîé) îöåíêå âåëè÷èíû âñåõ ðàññòîÿíèé/ñõîäñòâ. Äëÿ ýòîãî îáû÷-
íî ôîðìèðóþò íîâûå ïðåäñòàâëåíèÿ îáúåêòîâ â âèäå âåùåñòâåííûõ âåêòîðîâ ìà-
ëîé ðàçìåðíîñòè (ñì. îáçîð â [10]) èëè áèíàðíûõ âåêòîðîâ (ñì. îáçîð â [11]), ïî-
çâîëÿþùèõ ïðîâåñòè óñêîðåííóþ îöåíêó. Äðóãîé ïîäõîä çàêëþ÷àåòñÿ â ïîñòðîå-
íèè ïî áàçå òàêîé ñòðóêòóðû äàííûõ, èñïîëüçîâàíèå êîòîðîé ïðè âûïîëíåíèè
çàïðîñà ïîèñêà ïî ñõîäñòâó ïðèâåäåò ê óìåíüøåíèþ êîëè÷åñòâà âû÷èñëåíèé ñõîä-
ñòâà îáúåêòà-çàïðîñà ñ äðóãèìè îáúåêòàìè ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì.
Îòìåòèì, ÷òî àëãîðèòìû, ðàçðàáîòàííûå â ðàìêàõ îáîèõ ïîäõîäîâ, çà÷àñòóþ îáåñ-
ïå÷èâàþò óñêîðåíèå ïîèñêà çà ñ÷åò ïîëó÷åíèÿ ðåçóëüòàòîâ, íå ïîëíîñòüþ ñîâïàäà-
þùèõ ñ ðåçóëüòàòàìè (òî÷íîãî) ëèíåéíîãî ïîèñêà ïî ñõîäñòâó.
Íàñòîÿùèé îáçîð ïîñâÿùåí àëãîðèòìàì è ñòðóêòóðàì óñêîðåíèÿ ïîèñêà ïî
ñõîäñòâó, ðàçðàáîòàííûì â ðàìêàõ âòîðîãî ïîäõîäà, èñïîëüçóþùèì òîëüêî çíà-
÷åíèÿ ðàññòîÿíèé/ñõîäñòâ ìåæäó íåêîòîðûìè îáúåêòàìè è íå òðåáóþùèì ÿâíîãî
äîñòóïà ê ïðåäñòàâëåíèÿì îáúåêòîâ. Îòìåòèì, ÷òî äëÿ ìåòðè÷åñêèõ ðàññòîÿíèé
âûïîëíÿþòñÿ ìåòðè÷åñêèå àêñèîìû, âêëþ÷àÿ íåðàâåíñòâî òðåóãîëüíèêà, êîòîðîå
øèðîêî èñïîëüçóþò äëÿ óñêîðåíèÿ ïîèñêà.
 îòëè÷èå îò êëàññè÷åñêèõ ïóáëèêàöèé ïî äàííîé òåìå [12–15] â íàñòîÿùåì
îáçîðå ïðåäñòàâëåíû íîâûå ïîäõîäû è àëãîðèòìû, à òàêæå óñîâåðøåíñòâîâàíèÿ
óæå èçâåñòíûõ. Ââèäó îãðàíè÷åííîãî îáúåìà ñòàòüè â íåé èçëîæåíû ëèøü áàçî-
âûå èäåè, äåòàëüíóþ èíôîðìàöèþ ìîæíî íàéòè â ïðèâåäåííûõ ññûëêàõ. Â ðàçä. 1
ðàññìîòðåíû ðàñïðîñòðàíåííûå òèïû çàïðîñîâ ïîèñêà ïî ñõîäñòâó, îñíîâû ïî-
ñòðîåíèÿ èíäåêñíûõ ñòðóêòóð, ïðîáëåìû òî÷íîãî ïîèñêà è íåîáõîäèìîñòü ïðè-
áëèæåííîãî ïîèñêà äëÿ óñêîðåíèÿ âûïîëíåíèÿ çàïðîñà äëÿ ìíîãîìåðíûõ äàííûõ.
 ðàçä. 2 îáñóæäàþòñÿ èíäåêñíûå ñòðóêòóðû äëÿ ïîèñêà ïî ìåòðè÷åñêèì ðàññòîÿ-
íèÿì, à â ðàçä. 3 — ïî íåìåòðè÷åñêèì ðàññòîÿíèÿì, íåêîòîðûå èç ïîñëåäíèõ ìîæ-
íî àäàïòèðîâàòü äëÿ ïîèñêà ïî ìåðàì ñõîäñòâà.
1. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÓÑÊÎÐÅÍÈß ÏÎÈÑÊÀ ÏÎ ÑÕÎÄÑÒÂÓ.
ÎÑÍÎÂÍÛÅ ÏÐÈÍÖÈÏÛ
Îáúåêòû áàçû, êîòîðûå ÿâëÿþòñÿ îòâåòîì íà êîíêðåòíûé çàïðîñ ïîèñêà ïî
ñõîäñòâó, îïðåäåëÿþòñÿ òèïîì çàïðîñà è åãî ïàðàìåòðàìè, çàäàííûìè îáúåê-
òîì-çàïðîñîì (íå ïðèíàäëåæàùèì áàçå), ìåðîé ðàññòîÿíèÿ/ñõîäñòâà è äð. Äèà-
ïàçîííûé çàïðîñ (îáîçíà÷èì åãî rNN) âîçâðàùàåò îáúåêòû áàçû, ðàññòîÿíèÿ
êîòîðûõ îò îáúåêòà-çàïðîñà (ïî ìåðå ðàññòîÿíèÿ, çàäàííîé â çàïðîñå) íå ïðå-
âûøàþò ðàäèóñà çàïðîñà r. Ïðè íåêîòîðûõ r ðåçóëüòàòîì äèàïàçîííîãî çàïðî-
ñà ìîæåò áûòü ïóñòîå ìíîæåñòâî îáúåêòîâ èëè âñå îáúåêòû êîíêðåòíîé áàçû.
Çàïðîñ k áëèæàéøèõ ñîñåäåé (kNN) âîçâðàùàåò k îáúåêòîâ áàçû, áëèæàé-
øèõ ê îáúåêòó-çàïðîñó. Îáîçíà÷èì NN çàïðîñ kNN ïðè k �1, à òàêæå îáúåêò,
êîòîðûé ÿâëÿåòñÿ áëèæàéøèì ñîñåäîì. Çàïðîñ kNN ìîæíî, íàïðèìåð, âûïîë-
íèòü êàê çàïðîñ rNN ïðè r, ðàâíîì ðàññòîÿíèþ äî k-ãî NN (åñëè òàêîé r èçâåñ-
òåí), èëè ïîñëåäîâàòåëüíîñòüþ çàïðîñîâ rNN ñ óâåëè÷åíèåì r äî òåõ ïîð, ïîêà
êîëè÷åñòâî âîçâðàùåííûõ îáúåêòîâ íå äîñòèãíåò k [12–15]. Äàëåå ðàññìîòðåíû è
äðóãèå âàðèàíòû âûïîëíåíèÿ çàïðîñà kNN (ïîäðàçä. 1.2 è 1.5).
Îïðåäåëåíèÿ òèïîâ çàïðîñîâ â òåðìèíàõ ñõîäñòâà àíàëîãè÷íû.
Êðîìå çàïðîñîâ rNN è kNN, ñóùåñòâóþò è äðóãèå òèïû çàïðîñîâ ïîèñêà ïî ñõîäñòâó
[12–17], îäíàêî â íàñòîÿùåì îáçîðå èíäåêñíûå ñòðóêòóðû äëÿ íèõ íå ðàññìàòðèâàþòñÿ.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Ìíîãèå àëãîðèòìû óñêîðåíèÿ ïîèñêà ïî ñõîäñòâó èñïîëüçóþò äâóõýòàïíóþ
ñòðàòåãèþ ôèëüòðàöèè è óòî÷íåíèÿ (filter-and-refine, F&R). Íà ïåðâîì ýòàïå îñó-
ùåñòâëÿåòñÿ áûñòðûé îòáîð îáúåêòîâ-êàíäèäàòîâ. Ðåçóëüòàòû ïåðâîãî ýòàïà
óòî÷íÿþòñÿ íà âòîðîì ýòàïå (îáû÷íî ñ èñïîëüçîâàíèåì ëèíåéíîãî ïîèñêà ñðåäè
îáúåêòîâ-êàíäèäàòîâ ïî ìåðå ðàññòîÿíèÿ/ñõîäñòâà, çàäàííîé â çàïðîñå). Ñòðàòå-
ãèþ F&R èíîãäà ïðèìåíÿþò ìíîãîêðàòíî ïðè âûïîëíåíèè îäíîãî çàïðîñà.
1.1. Îáùèå ïðèíöèïû êîíñòðóèðîâàíèÿ è ïðèìåíåíèÿ èíäåêñíûõ
ñòðóêòóð. Èíäåêñíûå ñòðóêòóðû (ÈÑ èëè èíäåêñû) äëÿ ïîèñêà ïî ñõîäñòâó —
ýòî ñòðóêòóðû äàííûõ, â êîòîðûõ îáúåêòû áàçû îðãàíèçîâàíû òàêèì îáðàçîì,
÷òîáû óñêîðÿëîñü âûïîëíåíèå çàïðîñà ïî ñðàâíåíèþ ñ ëèíåéíûì ïîèñêîì çà
ñ÷åò óìåíüøåíèÿ êîëè÷åñòâà âû÷èñëÿåìûõ ðàññòîÿíèé/ñõîäñòâ.
Êîíñòðóèðóþò ÈÑ îôëàéí, ò.å. äî âûïîëíåíèÿ çàïðîñîâ. Äëÿ ïîñòðîåíèÿ ÈÑ
îáúåêòàì áàçû ñòàâÿòñÿ â ñîîòâåòñòâèå èíäåêñíûå çíà÷åíèÿ (êëþ÷è): îäíî èëè íå-
ñêîëüêî äëÿ êàæäîãî îáúåêòà. Îáû÷íî èíäåêñíûå çíà÷åíèÿ — ýòî âåùåñòâåííûå
÷èñëà èëè äèñêðåòíûå âåëè÷èíû. Íàïðèìåð, âåùåñòâåííûìè èíäåêñíûìè çíà÷å-
íèÿìè ìîãóò ÿâëÿòüñÿ ðàññòîÿíèÿ/ñõîäñòâà îáúåêòà ñ íåêîòîðûìè äðóãèìè îáúåê-
òàìè, à äèñêðåòíûìè — èäåíòèôèêàòîðû îáëàñòåé, êîòîðûì ïðèíàäëåæèò îáúåêò.
Èíäåêñíûå çíà÷åíèÿ îáúåêòîâ èñïîëüçóþò äëÿ êîíñòðóèðîâàíèÿ ÈÑ, â ÷àñò-
íîñòè, âûïîëíåíèåì ñëåäóþùèõ îïåðàöèé (íåêîòîðûõ èëè âñåõ):
— çàïîìèíàíèå èíäåêñíûõ çíà÷åíèé îáúåêòîâ (íàïðèìåð, ðàññòîÿíèé äî
äðóãèõ îáúåêòîâ);
— óïîðÿäî÷èâàíèå îáúåêòîâ áàçû (íàïðèìåð, ïî âîçðàñòàíèþ èëè óáûâà-
íèþ ðàññòîÿíèé äî äðóãèõ îáúåêòîâ);
— ðàçáèåíèå (partitioning) îáúåêòîâ áàçû íà ìíîæåñòâà (íàïðèìåð, â îäíî ìíî-
æåñòâî ïîìåùàþò îáúåêòû ñ îäèíàêîâûìè èíäåêñíûìè çíà÷åíèÿìè èëè ñ èíäåêñíû-
ìè çíà÷åíèÿìè â íåêîòîðîì äèàïàçîíå (â ÷àñòíîñòè, â äèàïàçîíå ðàññòîÿíèé äî íåêî-
òîðîãî îáúåêòà); ëèáî îáúåêò àññîöèèðóþò ñ åãî áëèæàéøèìè ñîñåäÿìè èç áàçû).
Ïðè êîíñòðóèðîâàíèè ÈÑ âîçìîæíî ïðèìåíåíèå è äðóãèõ îïåðàöèé. Îòìå-
òèì, ÷òî, åñëè èìååòñÿ äîñòóï ê ïðåäñòàâëåíèÿì îáúåêòîâ (íàïðèìåð, îáúåêòû
ÿâëÿþòñÿ âåêòîðàìè), èíäåêñèðîâàíèå ìîæåò âûïîëíÿòüñÿ íà îñíîâå íå òîëüêî
ðàññòîÿíèé/ñõîäñòâ, íî è èíûõ õàðàêòåðèñòèê ïðåäñòàâëåíèé (íàïðèìåð, äëÿ âåê-
òîðîâ ìîæíî èñïîëüçîâàòü çíà÷åíèÿ îòäåëüíûõ êîìïîíåíòîâ, ðåçóëüòàòû îïåðà-
öèé íàä âåêòîðàìè è ò.ä.).  íåêîòîðûõ ñëó÷àÿõ äëÿ îäíîé áàçû êîíñòðóèðóþò
íåñêîëüêî ÈÑ íà îñíîâå ðàçëè÷íûõ èíäåêñíûõ çíà÷åíèé.
Ñóùåñòâóþò ñòàòè÷åñêèå è äèíàìè÷åñêèå ÈÑ. Àëãîðèòì êîíñòðóèðîâàíèÿ
ñòàòè÷åñêèõ ÈÑ ïðåäïîëàãàåò íàëè÷èå âñåé áàçû îáúåêòîâ, êîíñòðóèðîâàíèå äè-
íàìè÷åñêèõ ÈÑ îñóùåñòâëÿåòñÿ îïåðàöèÿìè âñòàâêè îáúåêòîâ ïî ìåðå
ïîñòóïëåíèÿ äàííûõ.
Ïðè âûïîëíåíèè çàïðîñà ïîèñêà ïî ñõîäñòâó âû÷èñëÿþò èíäåêñíûå çíà÷å-
íèÿ îáúåêòà-çàïðîñà. Äàëåå ÈÑ è àëãîðèòì âûïîëíåíèÿ çàïðîñà çàäàííîãî òèïà
ïîçâîëÿþò îïðåäåëèòü, êàêèå îáúåêòû áàçû (èëè èõ ìíîæåñòâà) ìîãóò ÿâëÿòüñÿ
îòâåòîì (èëè ñîäåðæàòü îòâåò) íà çàïðîñ è ïîäëåæàò äàëüíåéøåé îáðàáîòêå, à êà-
êèå — íåò è äëÿ óñêîðåíèÿ ïîèñêà èõ ñëåäóåò îòáðîñèòü (discard), îáðåçàòü
(prunå) èëè èñêëþ÷èòü (eliminate).
 êà÷åñòâå ïðèìåðà ðàññìîòðèì ÈÑ äëÿ îáúåêòîâ, ïðåäñòàâëåííûõ îäíèì
÷èñëîì, ñ ðàññòîÿíèåì — ìîäóëåì ðàçíîñòè ÷èñåë. Êîíñòðóèðîâàíèå ïðîâåäåì
ñîðòèðîâêîé ýëåìåíòîâ ìàññèâà ðàçìåðíîñòè N , ñîîòâåòñòâóþùåãî N îáúåêòàì
áàçû. Äëÿ âûïîëíåíèÿ çàïðîñà NN ïðèìåíèì ïîèñê äèõîòîìèåé (binary search):
îáúåêò-çàïðîñ x ñðàâíèì ñ îáúåêòîì â ñåðåäèííîì (ìåäèàííîì) ýëåìåíòå ìàññè-
âà. Åñëè îíè íå ñîâïàäàþò, ïîëîâèíó ìàññèâà èñêëþ÷èì èç ðàññìîòðåíèÿ è ïå-
ðåéäåì ê ñåðåäèííîìó ýëåìåíòó îñòàâøåéñÿ ïîëîâèíû. Ïîâòîðåíèå ïðîöåäóðû
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 167
íàõîäèò NN çà âðåìÿ O N(log ) â õóäøåì ñëó÷àå. Çàòðàòû ïàìÿòè â ýòîé ÈÑ ñî-
ñòàâëÿþò O N( ), à âðåìÿ êîíñòðóèðîâàíèÿ O N N( log ) . Äëÿ âûïîëíåíèÿ çàïðîñà
kNN ðàññìîòðèì ñîñåäíèå îáúåêòû íàéäåííîãî NN. Äëÿ çàïðîñà rNN âûïîëíèì
äâà çàïðîñà NN ñ îáúåêòàìè-çàïðîñàìè: x r� è x r� ; îòâåòîì íà çàïðîñ rNN
ÿâëÿþòñÿ îáúåêòû ìàññèâà ìåæäó íàéäåííûìè îáúåêòàìè.
1.2. Ìåòîä âåòâåé è ãðàíèö â ïîèñêå ïî ñõîäñòâó. Êîíñòðóèðîâàíèå è èñ-
ïîëüçîâàíèå ìíîãèõ ÈÑ ìîæíî ðàññìàòðèâàòü êàê ïðèìåíåíèå ðàçíîâèäíîñòåé
ìåòîäà âåòâåé è ãðàíèö (branch and bound, B&B) ê ïîèñêó ïî ñõîäñòâó [18].
Îáúåêòû áàçû ðàçáèòû íà ïîäìíîæåñòâà, àññîöèèðîâàííûå ñ îáëàñòÿìè èíäåêñà.
Ðàçáèåíèÿ ìîãóò áûòü èåðàðõè÷åñêèìè (ïîäðàçä. 1.5), à òàêæå äèíàìè÷åñêèìè
(ò.å. â ïðîöåññå âûïîëíåíèÿ çàïðîñà, íàïðèìåð, ïîäðàçä. 2.1).
Ïðè âûïîëíåíèè çàïðîñà ïîèñêà çàïîìèíàåòñÿ òåêóùàÿ âåðõíÿÿ ãðàíèöà ðàñ-
ñòîÿíèÿ îò îáúåêòà-çàïðîñà äî îáúåêòà áàçû, êîòîðûé ìîæåò ÿâëÿòüñÿ îòâåòîì íà
çàïðîñ (ãðàíèöà ðåøåíèÿ). Òàê, äëÿ çàïðîñà rNN ýòà ãðàíèöà íåèçìåííà è ðàâíà r.
Äëÿ çàïðîñà kNN òåêóùàÿ ãðàíèöà ðåøåíèÿ ìîäèôèöèðóåòñÿ â õîäå âûïîëíåíèÿ
çàïðîñà è ðàâíà ðàññòîÿíèþ äî k-ãî îáúåêòà-êàíäèäàòà (èç òåêóùåãî ñïèñêà îáðà-
áîòàííûõ îáúåêòîâ ñ ìèíèìàëüíûìè ðàññòîÿíèÿìè äî îáúåêòà-çàïðîñà).
Êðîìå òîãî, îïðåäåëÿþòñÿ íèæíÿÿ è âåðõíÿÿ ãðàíèöû ðàññòîÿíèé îò îáúåê-
òà-çàïðîñà äî åùå íå îáðàáîòàííûõ ïîäìíîæåñòâ îáúåêòîâ áàçû. Åñëè íèæíÿÿ
ãðàíèöà áîëüøå ãðàíèöû ðåøåíèÿ, ïîäìíîæåñòâî èñêëþ÷àþò, èíà÷å ïåðåõîäÿò
ê åãî îáðàáîòêå. Åñëè âåðõíÿÿ ãðàíèöà ìåíüøå ãðàíèöû ðåøåíèÿ äëÿ çàïðîñà
rNN, ïîäìíîæåñòâî âêëþ÷àþò â îòâåò. Àíàëîãè÷íî îáðàáàòûâàþò èíäèâèäóàëü-
íûå îáúåêòû (ýòî èìååò ñìûñë, åñëè ãðàíèöû äëÿ íèõ âû÷èñëÿþòñÿ áûñòðåå, ÷åì
ðàññòîÿíèÿ äî îáúåêòà-çàïðîñà). Ñðåäè îáúåêòîâ, êîòîðûå íå óäàëîñü èñêëþ÷èòü,
âûïîëíÿþò ëèíåéíûé ïîèñê è ïðèíèìàþò ðåøåíèå î âêëþ÷åíèè èõ â îòâåò íà çà-
ïðîñ rNN (èëè â ñïèñîê òåêóùèõ êàíäèäàòîâ íà kNN). Òàêèå ïðîöåäóðû ïðîâî-
äÿò, ïîêà îñòàþòñÿ íåîáðàáîòàííûå ïîäìíîæåñòâà îáúåêòîâ. Â ðåçóëüòàòå, åñëè
óäàåòñÿ èñêëþ÷èòü ÷àñòü îáúåêòîâ áàçû áåç âû÷èñëåíèÿ ðàññòîÿíèé äî íèõ èëè
âîîáùå áåç èõ ðàññìîòðåíèÿ, ïîëó÷àåì ñóáëèíåéíûé ïîèñê (ò.å. óñêîðåííûé ïî
ñðàâíåíèþ ñ ëèíåéíûì). Êîíêðåòíûå àëãîðèòìû B&B èñïîëüçóþò ðàçëè÷íûå
ñïîñîáû ðàçáèåíèÿ áàçû íà ïîäìíîæåñòâà, î÷åðåäíîñòè îáõîäà ïîäìíîæåñòâ è
îïðåäåëåíèÿ ãðàíèö. Èõ ìîæíî ïðèìåíÿòü êàê äëÿ ìåòðè÷åñêèõ, òàê è äëÿ
íåìåòðè÷åñêèõ ðàññòîÿíèé/ñõîäñòâ, åñëè èìååòñÿ ìåõàíèçì îïðåäåëåíèÿ ãðàíèö.
1.3. Îïîðíûå îáúåêòû è îáëàñòè èíäåêñíîé ñòðóêòóðû è çàïðîñà. Äëÿ ïî-
ëó÷åíèÿ ãðàíèö ðàññòîÿíèé/ñõîäñòâ, ïðèìåíÿåìûõ â ìåòîäîëîãèè B&B, óäîáíî
îïåðèðîâàòü îáëàñòÿìè, êîòîðûì ïðèíàäëåæàò ìíîæåñòâà îáúåêòîâ áàçû. Â ÈÑ íà
îñíîâå ðàññòîÿíèé/ñõîäñòâ îáëàñòè îáû÷íî çàäàþò ðàçáèåíèåì ñôåðàìè è îáîá-
ùåííûìè ãèïåðïëîñêîñòÿìè, à òàêæå èõ âàðèàíòàìè è êîìáèíàöèÿìè [12–15]. Äëÿ
ýòîãî èñïîëüçóþò íåêîòîðûå âûäåëåííûå (èëè îïîðíûå) îáúåêòû áàçû. Ðàññòîÿ-
íèÿ äî îïîðíûõ îáúåêòîâ (ÎÎ) òàêæå ìîãóò íåïîñðåäñòâåííî ïðèìåíÿòüñÿ â êà-
÷åñòâå èíäåêñíûõ çíà÷åíèé èíäèâèäóàëüíûõ îáúåêòîâ áàçû.
Ñôåðè÷åñêîå ðàçáèåíèå çàäàåò ñôåðè÷åñêóþ îáëàñòü ñ öåíòðîì â ÎÎ oi è ðà-
äèóñîì ri . Åå âíóòðåííåé ÷àñòè ïðèíàäëåæàò âñå îáúåêòû y, äëÿ êîòîðûõ
dist ( , )o y ri i� . (Òàêèì îáðàçîì, äëÿ çàïðîñà rNN îáëàñòüþ çàïðîñà ÿâëÿåòñÿ ñôå-
ðè÷åñêàÿ îáëàñòü ñ öåíòðîì â îáúåêòå-çàïðîñå x è ðàäèóñîì r). Âíåøíåé ÷àñòè
ñôåðè÷åñêîé îáëàñòè ïðèíàäëåæàò âñå îáúåêòû y, äëÿ êîòîðûõ dist ( , )o y ri i� .
Êîëè÷åñòâî îáúåêòîâ â ïîäìíîæåñòâàõ ìîæíî ðåãóëèðîâàòü çíà÷åíèåì ri . Äëÿ
çàêëþ÷åíèÿ âñåãî ìíîæåñòâà îáúåêòîâ â ñôåðè÷åñêóþ îáëàñòü âûáèðàþò ÎÎ oi
è çàäàþò ïîêðûâàþùèé ðàäèóñ r oicov ( ) êàê ðàññòîÿíèå äî ñàìîãî óäàëåííîãî îáúåê-
òà ìíîæåñòâà. Â ÈÑ ïðèìåíÿþò îáëàñòè ìåæäó ñôåðàìè ñ îäíèì öåíòðîì è îòëè-
÷àþùèìèñÿ ðàäèóñàìè, à òàêæå îáëàñòè, çàäàâàåìûå ñ ïîìîùüþ ñôåð ñ ðàçëè÷-
íûìè öåíòðàìè, è äð. (ïîäðàçä. 2.2).
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Ãèïåðïëîñêîñòíîå ðàçáèåíèå çàäàþò äâóìÿ ÎÎ: oi è o j , è ïàðàìåòðîì �.
Ê îáëàñòè oi ïðèíàäëåæàò îáúåêòû y, äëÿ êîòîðûõ dist dist( , ) ( , )o y o yi j� � � ,
à ê îáëàñòè o j — îáúåêòû, äëÿ êîòîðûõ dist dist( , ) ( , )o y o yi j� � � [19]. Âûáîðîì
� ìîæíî ðåãóëèðîâàòü êîëè÷åñòâî îáúåêòîâ â îáëàñòÿõ. Ìíîæåñòâî ÎÎ çàäàåò
îáëàñòè Äèðèõëå (Dirichlet domain) — àíàëîã äèàãðàììû Âîðîíîãî, èñïîëüçóå-
ìîé â âåêòîðíûõ ïðîñòðàíñòâàõ. Îáëàñòü Äèðèõëå äëÿ oi — ýòî îáëàñòü, ãäå îáú-
åêòû áëèæå ê oi , ÷åì ê äðóãèì ÎÎ èç ìíîæåñòâà.
 ÈÑ íà îñíîâå ðàññòîÿíèé ïðèìåíÿþò ðàçëè÷íûå êîìáèíàöèè âàðèàíòîâ
ñôåðè÷åñêèõ è ãèïåðïëîñêîñòíûõ ðàçáèåíèé. Ñîãëàñíî ìåòîäîëîãèè B&B, åñëè
îáëàñòü çàïðîñà íå ïåðåñåêàåò îáëàñòü ÈÑ, ïîñëåäíþþ (è åå îáúåêòû) ìîæíî
èñêëþ÷èòü áåç óùåðáà äëÿ òî÷íîñòè ïîèñêà.
Íåêîòîðûå äîñòàòî÷íûå óñëîâèÿ èñêëþ÷åíèÿ îáëàñòåé ïðè èñïîëüçîâàíèè
ìåòðè÷åñêèõ ðàññòîÿíèé ðàññìîòðåíû â ïîäðàçä. 1.4. Äëÿ íåìåòðè÷åñêèõ ðàññòî-
ÿíèé è ñõîäñòâ â îáùåì ñëó÷àå íå ñóùåñòâóåò óíèâåðñàëüíûõ óñëîâèé èñêëþ÷å-
íèÿ, ïîýòîìó íóæíî ó÷èòûâàòü ñïåöèôè÷åñêèå ñâîéñòâà êîíêðåòíûõ íåìåòðèê
(ñì., íàïðèìåð, [20] è ïîäðàçä. 2.7, 3.1), ÷òî íå âñåãäà âîçìîæíî, ëèáî èñïîëüçî-
âàòü ÈÑ íå íà îñíîâå ìåòîäîëîãèè B&B (ïîäðàçä. 3.1.3 è 3.2–3.4).
1.4. Îáðàáîòêà îáëàñòåé è îáúåêòîâ íà îñíîâå âàðèàíòîâ íåðàâåíñòâà
òðåóãîëüíèêà. Â ÈÑ çàïîìíåíà èíôîðìàöèÿ îá îáëàñòÿõ èíäåêñà è/èëè î ðàññòîÿ-
íèÿõ dist ( , )o yi îáúåêòîâ áàçû y äî ÎÎ. Ïðè ïîñòóïëåíèè çàïðîñà rNN èçâåñòåí
åãî ðàäèóñ r è âû÷èñëÿåòñÿ ðàññòîÿíèå dist ( , )o xi îò îáúåêòà-çàïðîñà x äî ÎÎ. Äëÿ
ìåòðè÷åñêèõ ðàññòîÿíèé ýòà èíôîðìàöèÿ â ñî÷åòàíèè ñ âàðèàíòàìè íåðàâåíñòâà
òðåóãîëüíèêà [12–15] ïîçâîëÿåò èñêëþ÷èòü íåêîòîðûå ìíîæåñòâà îáúåêòîâ â îá-
ëàñòÿõ ÈÑ è èíäèâèäóàëüíûå îáúåêòû áàçû áåç âû÷èñëåíèÿ ðàññòîÿíèé dist ( , )x y .
Äëÿ ìåòðè÷åñêèõ ðàññòîÿíèé è ñôåðè÷åñêîãî ðàçáèåíèÿ îáëàñòü âíóòðè ñôå-
ðû ñ ÎÎ oi è r oicov ( ) è (ñôåðè÷åñêàÿ) îáëàñòü rNN çàïðîñà íå ïåðåñåêàþòñÿ, åñëè
dist cov( , ) ( )x o r r oi i� � . (1)
Îáëàñòü âíå ýòîé ñôåðû íå ïåðåñåêàåò îáëàñòü çàïðîñà, åñëè
dist cov( , ) ( )x o r o ri i� � . (2)
Îòìåòèì, ÷òî ïðè íåâûïîëíåíèè íåðàâåíñòâ (1), (2) ñîîòâåòñòâóþùèå îáëàñ-
òè ïåðåñåêàþòñÿ.
Äëÿ ìåòðè÷åñêèõ ðàññòîÿíèé è ãèïåðïëîñêîñòíîãî ðàçáèåíèÿ, åñëè x ïðèíàäëå-
æèò îáëàñòè oi , îáëàñòü o j ãàðàíòèðîâàííî íå ïåðåñåêàåò îáëàñòü çàïðîñà ïðè
dist dist( , ) ( , )o x o x rj i� � �2 � . (3)
Îòìåòèì, ÷òî ïðè íåâûïîëíåíèè íåðàâåíñòâà (3) è ïðè dist dist( , ) ( , )o x o xi j� �
� dist ( , )o oi j îáëàñòè òàêæå ìîãóò íå ïåðåñåêàòüñÿ [13, 21].
Òàêèì îáðàçîì, âûïîëíåíèå íåðàâåíñòâ (1)–(3) ãàðàíòèðóåò íåïåðåñå÷åíèå
îáëàñòè çàïðîñà ñîîòâåòñòâóþùèìè îáëàñòÿìè, è îáúåêòû áàçû òàêèõ îáëàñòåé
ìîæíî èñêëþ÷èòü èç äàëüíåéøåé îáðàáîòêè. Èíäèâèäóàëüíûå îáúåêòû ó ìîæíî
èñêëþ÷èòü, åñëè
| dist dist( , ) ( , ) |x o y o ri i� � , (4)
òàê êàê äëÿ íèõ ñîãëàñíî íåðàâåíñòâó òðåóãîëüíèêà dist ( , )x y r� .
Åñëè èìååòñÿ d îïîðíûõ îáúåêòîâ oi , i d�1, ,� , òî y ïîäëåæèò èñêëþ÷åíèþ
ïðè âûïîëíåíèè (4) õîòÿ áû äëÿ îäíîãî oi . Ýòî óñëîâèå èñêëþ÷åíèÿ ìîæíî ïåðå-
ïèñàòü ñ èñïîëüçîâàíèåì âåêòîðíîãî ïðåäñòàâëåíèÿ � ( )y , ãäå çíà÷åíèå êîìïî-
íåíòà � i iy y o( ) ( , )� dist , êàê max | dist disti i ix o y o L x y r( , ) ( , ) | ( ( ), ( ))� � �� � � ,
çäåñü L� — ðàññòîÿíèå ×åáûøåâà. Îòìåòèì, ÷òî ýòî ñæèìàþùåå ïðåîáðàçîâà-
íèå: dist ( , ) ( ( ), ( ))x y L x y� � � � [12, 13, 22].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 169
Ðàññìîòðåííûå è äðóãèå óñëîâèÿ èñêëþ÷åíèÿ âàðèàíòàìè íåðàâåíñòâà òðåó-
ãîëüíèêà (íàïðèìåð, [23]) ìîæíî ïðèìåíÿòü ñîâìåñòíî, óâåëè÷èâàÿ âåðîÿòíîñòü
èñêëþ÷åíèÿ. Íåêîòîðûå ìåòðè÷åñêèå ðàññòîÿíèÿ èìåþò äîïîëíèòåëüíûå ñâîé-
ñòâà, êîòîðûå ïîçâîëÿþò áîëåå ýôôåêòèâíîå èñêëþ÷åíèå, ÷åì íåðàâåíñòâî
òðåóãîëüíèêà (ïîäðàçä. 2.7).
1.5. Äðåâîâèäíûå èíäåêñíûå ñòðóêòóðû è àëãîðèòìû èõ îáõîäà. Äëÿ
óñêîðåíèÿ ïîñòðîåíèÿ è èñïîëüçîâàíèÿ ÈÑ â ðÿäå ñëó÷àåâ ðàçáèåíèå áàçû íà
ìíîæåñòâà îáúåêòîâ ïðîâîäÿò èåðàðõè÷åñêè: ïîëó÷åííûå â ðåçóëüòàòå ðàçáèåíèÿ
ìíîæåñòâà ðåêóðñèâíî ðàçáèâàþò íà áîëåå ìåëêèå ïîäìíîæåñòâà. ×àñòî èåðàð-
õè÷åñêèå èíäåêñû äëÿ ïîèñêà ïî ñõîäñòâó èìåþò äðåâîâèäíóþ ñòðóêòóðó. Ìíî-
æåñòâó îáúåêòîâ áàçû (è èõ îáëàñòè) îáû÷íî ñîîòâåòñòâóåò óçåë äåðåâà. Âåðõíèé
(êîðíåâîé) óçåë ñîîòâåòñòâóåò âñåì îáúåêòàì áàçû, à óçëû-ñûíîâüÿ — ïîäìíî-
æåñòâàì îáúåêòîâ óçëà-ðîäèòåëÿ. Â äåðåâüÿõ óçåë-ñûí èìååò ðîâíî îäíîãî ðîäè-
òåëÿ. ×åì íèæå óðîâåíü óçëîâ, òåì ìåíüøå îáúåêòîâ â èõ ïîäìíîæåñòâå è òåì
ìåíüøèå èõ îáëàñòè ðàçáèåíèÿ. Óçåë ñîäåðæèò èíôîðìàöèþ, ïîçâîëÿþùóþ ïî
èíäåêñíûì çíà÷åíèÿì îòíåñòè îáúåêò ê åãî óçëàì-ñûíîâüÿì è èõ îáëàñòÿì.
Îáúåêòû áàçû èëè ññûëêè íà íèõ ñîäåðæàòñÿ â êîðçèíàõ. Â äåðåâüÿõ êîðçèíàìè
÷àñòî ÿâëÿþòñÿ ëèñòüÿ (óçëû, íå èìåþùèå ñûíîâåé). Êîðçèíå ëèñòà ìîæåò ïðè-
íàäëåæàòü îäèí èëè áîëåå îáúåêòîâ áàçû.
Ïðè âûïîëíåíèè çàïðîñà NN íà îñíîâå ìåòîäà B&B ïîðÿäîê îáõîäà óçëîâ
(îáëàñòåé) ñóùåñòâåííî âëèÿåò íà âðåìÿ ïîèñêà, òàê êàê áûñòðîå íàõîæäåíèå òå-
êóùåãî áëèæàéøåãî ñîñåäà ñ ìàëûì ðàññòîÿíèåì îò îáúåêòà-çàïðîñà óìåíüøàåò
îáëàñòü çàïðîñà, ÷òî ìîæåò çíà÷èòåëüíî ñîêðàòèòü êîëè÷åñòâî ïîäëåæàùèõ
îáðàáîòêå îáëàñòåé èíäåêñà.
 äðåâîâèäíûõ ÈÑ äëÿ áûñòðîãî íàõîæäåíèÿ «õîðîøåãî» òåêóùåãî NN âíà-
÷àëå âûïîëíÿþò ñïóñê ïî äåðåâó èç êîðíåâîãî óçëà â ëèñòîâîé [13]. Äëÿ ïåðåõî-
äà â êàæäîì óçëå âûáèðàþò óçåë-ñûí (îáëàñòü) ñ ìèíèìàëüíûì ðàññòîÿíèåì îò
îáúåêòà-çàïðîñà (îáû÷íî îáëàñòü, êîòîðîé ïðèíàäëåæèò îáúåêò-çàïðîñ).  êîðçè-
íå ëèñòà ëèíåéíûì ïîèñêîì íàõîäÿò áëèæàéøèé îáúåêò è èñïîëüçóþò â êà÷åñòâå
òåêóùåãî NN. Çà÷àñòóþ íàéäåííûé îáúåêò ÿâëÿåòñÿ õîðîøèì êàíäèäàòîì, îäíà-
êî òî÷íûé NN ìîæåò íàõîäèòüñÿ â äðóãèõ êîðçèíàõ. Ïîýòîìó ïðîäîëæàþò îáõîä
óçëîâ äåðåâà â ïîðÿäêå, êîòîðûé çàâèñèò îò àëãîðèòìà îáõîäà.
Ïðè àëãîðèòìå îáõîäà depth-first [13] äàëåå âûïîëíÿþò îáðàòíîå ïðîñëåæè-
âàíèå (backtracking) — èç ïîñåùåííîãî ëèñòîâîãî óçëà âîçâðàùàþòñÿ íà óçåë-ðî-
äèòåëü è ïåðåõîäÿò íà äðóãèå åãî ëèñòîâûå óçëû, åñëè èõ îáëàñòè ïåðåñåêàþò òå-
êóùóþ îáëàñòü çàïðîñà. Òåêóùèé ðàäèóñ ìîäèôèöèðóþò, êîãäà íàõîäÿò áîëåå
áëèçêèé ê çàïðîñó îáúåêò áàçû. Ïî èñ÷åðïàíèè ëèñòîâûõ óçëîâ òåêóùåãî óçëà
âûïîëíÿåòñÿ âîçâðàò ê åãî óçëó-ðîäèòåëþ âåðõíåãî óðîâíÿ è ðåêóðñèâíî ïðîäîë-
æàåòñÿ îáõîä íåïîñåùåííûõ óçëîâ-ñûíîâåé, îáëàñòè êîòîðûõ ïåðåñåêàþò òåêó-
ùóþ îáëàñòü çàïðîñà. Ôàêòè÷åñêè óêàçàííûé ïîðÿäîê îáõîäà îïðåäåëÿåòñÿ
ïîðÿäêîì èçâëå÷åíèÿ óçëîâ èç ñòåêà (LIFO), êóäà çàíîñÿòñÿ ñûíîâüÿ êàæäîãî
óçëà ïðè åãî ïîñåùåíèè.
Ïðè àëãîðèòìå îáõîäà best-first [13] âû÷èñëåííûå ïðè ïåðâîíà÷àëüíîì ñïóñ-
êå èç êîðíÿ â ëèñò ðàññòîÿíèÿ äî óçëîâ (èõ îáëàñòåé) ðàçëè÷íûõ óðîâíåé çàíîñÿò
â ïðèîðèòåòíóþ î÷åðåäü ñ ñîðòèðîâêîé ïî óâåëè÷åíèþ. Äëÿ äàëüíåéøåãî îáõîäà
èç ïðèîðèòåòíîé î÷åðåäè èçâëåêàþò ïåðâûé óçåë è îáõîäÿò åãî (íåïîñåùåííûå)
óçëû-ñûíîâüÿ, îáëàñòè êîòîðûõ ïåðåñåêàþò òåêóùóþ îáëàñòü çàïðîñà, äîáàâëÿÿ
â î÷åðåäü óçëû ñ èõ ðàññòîÿíèÿìè è ìîäèôèöèðóÿ òåêóùèé ðàäèóñ çàïðîñà. Äëÿ
òî÷íîãî ïîèñêà îáõîä ïðåêðàùàþò, êîãäà ðàññòîÿíèå äî ïåðâîãî óçëà î÷åðåäè
ïðåâûøàåò òåêóùèé ðàäèóñ çàïðîñà. Ïðè ïðèáëèæåííîì ïîèñêå best-first
ïîçâîëÿåò áûñòðî íàõîäèòü «õîðîøèõ» ñîñåäåé è îñòàíàâëèâàòü ïîèñê ðàíüøå,
÷åì ïðè òî÷íîì.
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
1.6. Îò òî÷íîãî ê ïðèáëèæåííîìó ïîèñêó ïî ñõîäñòâó. Âðåìÿ âûïîëíåíèÿ
çàïðîñà â ÈÑ íàèáîëåå èññëåäîâàíî äëÿ âåêòîðíûõ äàííûõ. Àíàëèç âñåõ èçâåñòíûõ
àëãîðèòìîâ òî÷íîãî ïîèñêà ïî ñõîäñòâó ïîêàçûâàåò, ÷òî çàòðàòû âðåìåíè èëè ïàìÿ-
òè ðàñòóò ýêñïîíåíöèàëüíî ñ óâåëè÷åíèåì ðàçìåðíîñòè äàííûõ D [16, 17]. Ýòî
ÿâëåíèå íàçûâàþò «ïðîêëÿòèåì ðàçìåðíîñòè» (curse of dimensionality) â ïîèñêå
ïî ñõîäñòâó [12, 17, 24, 25]. Äëÿ àëãîðèòìîâ ñ çàòðàòàìè ïàìÿòè, áëèçêèìè ê ëè-
íåéíûì, ëó÷øåå èçâåñòíîå âðåìÿ min ( , )( )2O D DN äëÿ ñëó÷àéíîãî îáúåêòà-çàïðî-
ñà [17] (ò.å. äëÿ ñðåäíåãî ñëó÷àÿ è òåì áîëåå äëÿ õóäøåãî). Ïîýòîìó äëÿ áàç
ñ äîñòèæèìûì N ñ ðîñòîì D òî÷íûé ïîèñê âûðîæäàåòñÿ â ëèíåéíûé, äàæå ïðè
íå ñëèøêîì áîëüøèõ D , ÷òî ïîäòâåðæäàåòñÿ è íà ïðàêòèêå [24]. Äëÿ îáùèõ ìåò-
ðè÷åñêèõ ïðîñòðàíñòâ ñ íåèçâåñòíûì ïðåäñòàâëåíèåì îáúåêòîâ ïðîêëÿòèå ðàç-
ìåðíîñòè îáñóæäàåòñÿ â òåðìèíàõ âíóòðåííåé ðàçìåðíîñòè (intrinsic dimension)
[23, 26–33]. Íàïðèìåð, â [12] ýòî îòíîøåíèå êâàäðàòà ñðåäíåãî çíà÷åíèÿ è äèñ-
ïåðñèè ðàññòîÿíèé ìåæäó îáúåêòàìè áàçû.
Ïðåîäîëåòü (òî÷íåå, îáîéòè) ïðîêëÿòèå ðàçìåðíîñòè äëÿ ïîèñêà ïî ñõîäñòâó
óäàåòñÿ ïåðåõîäîì îò òî÷íîãî ê áîëåå áûñòðîìó, íî ïðèáëèæåííîìó ïîèñêó, êî-
òîðûé äîïóñêàåò îòëè÷èå ðåçóëüòàòîâ îò òî÷íîãî ïîèñêà. Íà ïðàêòèêå îí âîñòðå-
áîâàí, ïîñêîëüêó äëÿ ìíîãèõ ïðèëîæåíèé äîñòàòî÷íî ïîëó÷àòü ïðèáëèæåííûå
ðåçóëüòàòû, íî áûñòðî. Ìíîãèå ïîäõîäû ê óñêîðåíèþ òî÷íîãî ïîèñêà ìîæíî
ðàññìàòðèâàòü êàê îáðàáîòêó ïðè âûïîëíåíèè çàïðîñà òîëüêî ÷àñòè òåõ îáúåêòîâ
áàçû, êîòîðûå íåîáõîäèìî îáðàáîòàòü ïðè òî÷íîì ïîèñêå.  èñêëþ÷åííîé ÷àñòè
ìîãóò ñîäåðæàòüñÿ îáúåêòû, ÿâëÿþùèåñÿ òî÷íûì ðåçóëüòàòîì. Ïðè àãðåññèâíîé
îáðåçêå (aggressive pruning) [34] äîïîëíèòåëüíî ê ïîäìíîæåñòâàì, èñêëþ÷àåìûì
òî÷íûì ïîèñêîì, èñêëþ÷àþò íåêîòîðûå äðóãèå îáëàñòè, íàïðèìåð, óìåíüøàÿ òå-
êóùèé ðàäèóñ çàïðîñà.  ðÿäå ñëó÷àåâ ýòî ïîçâîëÿåò ïîëó÷èòü ãàðàíòèðîâàííîå
îòíîøåíèå ðàññòîÿíèé îáúåêòà-çàïðîñà äî íàéäåííîãî è òî÷íîãî NN. Ðàííèé
îñòàíîâ (early stopping) [34] ïðåêðàùàåò ïîèñê äî ãàðàíòèðîâàííîãî äîñòèæåíèÿ
òî÷íîãî ðåçóëüòàòà. Êðèòåðèåì îñòàíîâà ìîæåò ÿâëÿòüñÿ, íàïðèìåð, êîëè÷åñòâî
îáðàáîòàííûõ îáúåêòîâ áàçû. Êîëè÷åñòâåííûõ ãàðàíòèé êà÷åñòâà ðåçóëüòàòîâ
ïîèñêà îáû÷íî íå ñóùåñòâóåò. Ðàííèé îñòàíîâ ïðèìåíèì äëÿ àëãîðèòìîâ ëþáîãî
òèïà, êîòîðûå áûñòðî íàõîäÿò òî÷íûõ áëèæàéøèõ ñîñåäåé ëèáî èõ õîðîøåå
ïðèáëèæåíèå. Âàðèàíòû àãðåññèâíîé îáðåçêè è ðàííåãî îñòàíîâà, à òàêæå
ðàçëè÷íûå òèïû ãàðàíòèé êà÷åñòâà ðåçóëüòàòîâ ïðèáëèæåííîãî ïîèñêà
îáñóæäàþòñÿ â [34].
Íà ïðàêòèêå êà÷åñòâî ðåçóëüòàòîâ ïðèáëèæåííîãî ïîèñêà (ñòåïåíü èõ îòëè÷èÿ
îò ðåçóëüòàòîâ òî÷íîãî ïîèñêà) îöåíèâàþò â ýêñïåðèìåíòàõ íà êîíêðåòíûõ áàçàõ.
×àñòî èñïîëüçóþò ìåðû êà÷åñòâà âûïîëíåíèÿ êîíêðåòíîãî çàïðîñà, èçâåñòíûå
êàê [35] ïîëíîòà (recall), ðàâíàÿ n n1 2/ , è òî÷íîñòü (precision), ðàâíàÿ n n1 3/ , ãäå
n1 — êîëè÷åñòâî âîçðàùåííûõ îáúåêòîâ, ñîâïàâøèõ ñ ðåëåâàíòíûìè, n2 — êîëè-
÷åñòâî ðåëåâàíòíûõ çàïðîñó îáúåêòîâ â áàçå, n3 — êîëè÷åñòâî âîçðàùåííûõ îáú-
åêòîâ áàçû. Äëÿ çàïðîñà kNN n n k2 3� � , ïîýòîìó òî÷íîñòü ðàâíà ïîëíîòå.
«Õîðîøèìè» ñîñåäÿìè ìîãóò ÿâëÿòüñÿ íå òîëüêî òî÷íûå, íî è îáúåêòû áàçû,
áëèçêèå ê íèì. Ïîýòîìó êà÷åñòâî ïîèñêà òàêæå èçìåðÿþò îòíîøåíèåì ñóììû
(èëè ñðåäíåãî) ðàññòîÿíèé îáúåêòà-çàïðîñà äî âîçâðàùåííûõ îáúåêòîâ ê ñîîòâåò-
ñòâóþùåé âåëè÷èíå äëÿ òî÷íîãî ðåçóëüòàòà.
Ïðè âûïîëíåíèè ìíîæåñòâà çàïðîñîâ ïîëó÷åííûå äëÿ èíäèâèäóàëüíûõ çà-
ïðîñîâ çíà÷åíèÿ ìåð êà÷åñòâà óñðåäíÿþò. Òàê, äëÿ çàïðîñà NN ïîëíîòó (ðàâ-
íóþ òî÷íîñòè) èçìåðÿþò êàê ïðîöåíò çàïðîñîâ, äëÿ êîòîðûõ áûë âîçâðàùåí
òî÷íûé NN [36].
Êîìïðîìèññ êà÷åñòâà è âðåìåíè ïîèñêà ïî ñõîäñòâó îáû÷íî îáåñïå÷èâàåòñÿ
âûáîðîì ïàðàìåòðîâ ÈÑ. Ïîýòîìó ÈÑ äëÿ ïðèáëèæåííîãî ïîèñêà ñðàâíèâàþò ïî
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 171
(óñðåäíåííîìó) âðåìåíè âûïîëíåíèÿ çàïðîñà ïðè ôèêñèðîâàííîì ïàðàìåòðå êà-
÷åñòâà ïîèñêà èëè ïî çíà÷åíèþ ìåðû êà÷åñòâà ïîèñêà ïðè îäèíàêîâîì âðåìåíè
ïîèñêà. Âàæíîé õàðàêòåðèñòèêîé òàêæå ÿâëÿþòñÿ çàòðàòû ïàìÿòè íà ÈÑ
(êâàäðàòè÷íûå çàòðàòû îáû÷íî íåïðèåìëåìû).
Äëÿ òî÷íîãî ïîèñêà îïðåäåëÿåòñÿ ëó÷øàÿ ÈÑ ïî ìèíèìàëüíîìó âðåìåíè ïîèñêà.
2. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÏÎÈÑÊÀ ÏÎ ÌÅÒÐÈ×ÅÑÊÈÌ ÐÀÑÑÒÎßÍÈßÌ
Áîëüøèíñòâî ðàññìàòðèâàåìûõ â äàííîì ðàçäåëå ÈÑ ïðåäíàçíà÷åíî äëÿ òî÷-
íîãî âûïîëíåíèÿ çàïðîñîâ ïîèñêà ïî ñõîäñòâó (rNN, à òàêæå kNN) âàðèàíòà-
ìè ìåòîäà B&B (ñì. ïîäðàçä. 1.2) ñ èñêëþ÷åíèåì îáëàñòåé è îáúåêòîâ ðàçíî-
âèäíîñòÿìè íåðàâåíñòâà òðåóãîëüíèêà (ñì. ïîäðàçä. 1.4). Ïîýòîìó ñëåäóåò
îæèäàòü ýêñïîíåíöèàëüíîé çàâèñèìîñòè âðåìåíè âûïîëíåíèÿ çàïðîñà îò âíóò-
ðåííåé ðàçìåðíîñòè äàííûõ (ñì. ïîäðàçä. 1.6). Íà ïðàêòèêå ýòî ïðèâîäèò
ê øèðîêîìó äèàïàçîíó âðåìåíè ïîèñêà O N( )� äëÿ íåêîòîðîãî 0 1� �� [37],
ãäå � çàâèñèò îò îñîáåííîñòåé äàííûõ, çàïðîñîâ, à òàêæå ìåðû ðàññòîÿíèÿ
è ÈÑ. Çà÷àñòóþ íå èìååòñÿ àíàëèòè÷åñêèõ îöåíîê âðåìåíè ïîèñêà, èñïîëüçóþò-
ñÿ ýêñïåðèìåíòàëüíûå îöåíêè íà êîíêðåòíûõ áàçàõ. Âî ìíîãèõ ñëó÷àÿõ âîçìîæ-
íî óñêîðåíèå ïîèñêà çà ñ÷åò ïîòåðè ãàðàíòèé òî÷íîñòè òàêèìè ñòàíäàðòíûìè
ïðèåìàìè, êàê ðàííèé îñòàíîâ èëè àãðåññèâíàÿ îáðåçêà (ñì. ïîäðàçä. 1.6).
 ðàçä. 2 ðàññìîòðåíû ñëåäóþùèå òèïû ÈÑ: íåèåðàðõè÷åñêèå íà îñíîâå
ïðåäâû÷èñëåííûõ ðàññòîÿíèé (ïîäðàçä. 2.1); äðåâîâèäíûå ñ ðàçáèåíèåì íà îá-
ëàñòè ãèïåðñôåðàìè è ãèïåðïëîñêîñòÿìè, à òàêæå èõ óñîâåðøåíñòâîâàíèÿ (ïîä-
ðàçä. 2.2); íà îñíîâå ÈÑ äëÿ ñêàëÿðíûõ è âåêòîðíûõ äàííûõ (ïîäðàçä. 2.3); äå-
ðåâüÿ ñîñåäñòâà (ïîäðàçä. 2.4); ñ íåèåðàðõè÷åñêèì ðàçáèåíèåì íà îáëàñòè (ïîä-
ðàçä. 2.5). Â ïîäðàçä. 2.6 îáñóæäàåòñÿ âûáîð ÎÎ, à â ïîäðàçä. 2.7 — óñëîâèÿ
èñêëþ÷åíèÿ áåç èñïîëüçîâàíèÿ íåðàâåíñòâà òðåóãîëüíèêà.
2.1. Íåèåðàðõè÷åñêèå èíäåêñíûå ñòðóêòóðû íà îñíîâå çàïîìèíàíèÿ ðàñ-
ñòîÿíèé ìåæäó îáúåêòàìè. Äëÿ êîíñòðóèðîâàíèÿ ÈÑ AESA [38, 39] âû÷èñëÿåò-
ñÿ ìàòðèöà ðàññòîÿíèé ìåæäó âñåìè îáúåêòàìè áàçû. Ïðè âûïîëíåíèè çàïðîñà
âû÷èñëÿþò ðàññòîÿíèå dist( , )x oi îò îáúåêòà-çàïðîñà x äî íåêîòîðîãî ÎÎ (îáúåêòà
áàçû oi , íàïðèìåð, âûáðàííîãî ñëó÷àéíî) è èñêëþ÷àþò îáúåêòû áàçû y, äëÿ êî-
òîðûõ âûïîëíÿåòñÿ íåðàâåíñòâî (4). Èç îñòàâøèõñÿ îáúåêòîâ áàçû âûáèðàþò
ñëåäóþùèé ÎÎ è ïîâòîðÿþò ïðîöåäóðó èñêëþ÷åíèÿ. Ïðîöåññ ïðîäîëæàþò, ïîêà
íå èñ÷åðïàåòñÿ ìíîæåñòâî ÎÎ ëèáî äî çàäàííîãî êîëè÷åñòâà îñòàâøèõñÿ îáúåê-
òîâ. Ñðåäè ýòèõ îáúåêòîâ-êàíäèäàòîâ âûïîëíÿþò ëèíåéíûé ïîèñê. Ïðåäëîæåí
ðÿä ýâðèñòè÷åñêèõ ïðîöåäóð âûáîðà î÷åðåäíûõ OO, ïîâûøàþùèõ ýôôåêòèâ-
íîñòü èñêëþ÷åíèÿ, íàïðèìåð iAESA [40]. Çàòðàòû ïàìÿòè íà õðàíåíèå ìàòðèöû
ðàññòîÿíèé AESA ñîñòàâëÿþò O N( )2 , âûïîëíåíèå çàïðîñà òðåáóåò îò O N( ) äî
O N( )2 îáðàùåíèé ê ìàòðèöå ðàññòîÿíèé. Ýêñïåðèìåíòàëüíî (äëÿ äàííûõ ìàëîé
ðàçìåðíîñòè) ñðåäíåå âðåìÿ âûïîëíåíèÿ çàïðîñà ïîñòîÿííî [38].
Äëÿ áîëüøèõ N êâàäðàòè÷íûå çàòðàòû ïàìÿòè AESÀ íåïðèåìëåìû. Äëÿ
óìåíüøåíèÿ ðàçìåðà ìàòðèöû ðàññòîÿíèé â ÈÑ LAESA [41] â êà÷åñòâå ÎÎ èñ-
ïîëüçóþò íå âñå, à ôèêñèðîâàííîå ïîäìíîæåñòâî îáúåêòîâ áàçû. Ñêîðîñòü èñêëþ-
÷åíèÿ ïîâûøàþò ïðèìåíåíèåì ïîèñêà äèõîòîìèåé (ñì. ïîäðàçä. 1.1) äëÿ îïðåäå-
ëåíèÿ îáúåêòîâ-êàíäèäàòîâ y, äëÿ êîòîðûõ dist( , )y oi íàõîäèòñÿ â äèàïàçîíå
[ ( , ) , ( , )dist distx o r x o ri i� � ] [42, 43]. Îòìåòèì, ÷òî ðåçóëüòàòû îòáîðà êàíäèäà-
òîâ, òîæäåñòâåííûå (L)AESA, äàåò ëèíåéíûé ïîèñê ïî ðàññòîÿíèþ L� âåêòîðíûõ
ïðåäñòàâëåíèé îáúåêòîâ, ñ êîìïîíåíòàìè — ðàññòîÿíèÿìè äî ÎÎ (ñì. ïîä-
ðàçä. 1.4). Óñêîðåíèå íàõîæäåíèÿ ïåðåñå÷åíèÿ ìíîæåñòâ êàíäèäàòîâ, ïîëó÷åííûõ
äëÿ êàæäîãî ÎÎ ñ èñïîëüçîâàíèåì ñæàòîãî ïðåäñòàâëåíèÿ ïåðåñòàíîâîê [44],
ïðåäëîæåíî â [45]. Ïðèáëèæåííûé ïîèñê ïî ñõîäñòâó â (L)AESA ðàññìîòðåí
â [40] (ðàííèé îñòàíîâ) è [46] (àãðåññèâíàÿ îáðåçêà) è ññûëêàõ ê íèì.
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
 ðàáîòå [47] ÈÑ EPT ñîñòîèò èç çàäàííîãî êîëè÷åñòâà ãðóïï ÎÎ.  îòëè÷èå
îò (L)AESA â êàæäîé ãðóïïå N îáúåêòîâ áàçû ðàçáèòû íà íåïåðåñåêàþùèåñÿ
ïîäìíîæåñòâà ñî ñâîèì «õîðîøèì» ÎÎ äëÿ ïîäìíîæåñòâà. Äëÿ êàæäîãî îáúåêòà
ãðóïïû çàïîìèíàåòñÿ åãî ÎÎ è ðàññòîÿíèå äî íåãî. Äëÿ óëó÷øåíèÿ èñêëþ÷åíèÿ
è ñîîòâåòñòâóþùåãî óñêîðåíèÿ ïîèñêà êîëè÷åñòâî è ñîñòàâ ÎÎ â ãðóïïå îïòèìè-
çèðóþò (ïîäðàçä 2.6). Â ýêñïåðèìåíòàõ EPT ðàáîòàåò áûñòðåå LAESA, SAT è LC
(ïîäðàçä. 2.4 è 2.5) ïðè ìåíüøèõ çàòðàòàõ ïàìÿòè.
2.2. Êëàññè÷åñêèå ìåòðè÷åñêèå äåðåâüÿ è èõ óñîâåðøåíñòâîâàíèÿ. Òè-
ïè÷íûå èåðàðõè÷åñêèå ÈÑ íà îñíîâå ðàññòîÿíèé ñ ðàçáèåíèåì îáúåêòîâ áàçû íà
ìíîæåñòâà — ýòî ìåòðè÷åñêèå äåðåâüÿ (metric trees) [48] è èõ ðàçíîâèäíîñòè. Äëÿ
ðàçáèåíèÿ â îñíîâíîì èñïîëüçóþò ñôåðû, ãèïåðïëîñêîñòè (ñì. ïîäðàçä. 1.3) è èõ
âàðèàíòû, ïðèìåíÿþò òàêæå çàïîìèíàíèå ðàññòîÿíèé (îáúåêòîâ áàçû äî ÎÎ,
ìåæäó ÎÎ). Ïîèñê îñóùåñòâëÿþò âàðèàíòàìè F&R è B&B (ñì. ðàçä. 1).
Àíàëèç âðåìåíè âûïîëíåíèÿ çàïðîñà òî÷íîãî ïîèñêà îáû÷íî ïðîâîäÿò äëÿ
ñðåäíåãî ñëó÷àÿ. Ïðè äîñòàòî÷íî ìàëîì ðàäèóñå îáëàñòè çàïðîñà (ò.å. ïðè ìèíè-
ìàëüíîì îáðàòíîì ïðîñëåæèâàíèè) äëÿ ñáàëàíñèðîâàííûõ äåðåâüåâ (ó êîòîðûõ
âñå ïóòè îò êîðíÿ ê ëèñòüÿì îòëè÷àþòñÿ íå áîëåå ÷åì íà 1) âðåìÿ ñîñòàâëÿåò
O N( )log (âðåìÿ ñïóñêà èç êîðíÿ â ëèñò). Äëÿ äàííûõ áàçû ñ áîëüøîé
âíóòðåííåé ðàçìåðíîñòüþ âðåìÿ äîñòèãàåò O N( ).
2.2.1. Ìåòðè÷åñêèå äåðåâüÿ íà îñíîâå ñôåðè÷åñêèõ îáëàñòåé.  [49, 50]
ðåêóðñèâíî ñòðîÿò ÈÑ VP-tree êàê áèíàðíîå äåðåâî, ðàçáèâàÿ ìíîæåñòâî îáúåê-
òîâ áàçû íà ïîäìíîæåñòâà ñôåðè÷åñêèìè îáëàñòÿìè (ñì. ïîäðàçä. 1.3).  êîðíå
äåðåâà âûáèðàþò â êà÷åñòâå ÎÎ îäèí èç îáúåêòîâ áàçû è òàêîé ðàäèóñ ñôåðû
ñ öåíòðîì â ýòîì ÎÎ, ÷òîáû ïîëîâèíà îáúåêòîâ áàçû îêàçàëàñü âíóòðè íåå, à ïî-
ëîâèíà — âíå ñôåðû (ðàäèóñ ðàâåí ìåäèàííîìó çíà÷åíèþ ðàññòîÿíèé äî ÎÎ).
Ïîääåðåâüÿ êîíñòðóèðóþò ðåêóðñèâíî, âûáèðàÿ ÎÎ â êàæäîì ïîäìíîæåñòâå. Äå-
ðåâî ïîëó÷àåòñÿ ñáàëàíñèðîâàííûì (ïî âûñîòå è ÷èñëó îáúåêòîâ â óçëàõ îäíîãî
óðîâíÿ). Âðåìÿ ïîñòðîåíèÿ ñîñòàâëÿåò O N N( log ), à çàòðàòû ïàìÿòè O N( ). Çàï-
ðîñû âûïîëíÿþò ìåòîäîì B&B, ïåðåõîä íà óçëû-ñûíîâüÿ (îäèí èëè îáà) îñóùå-
ñòâëÿþò ñîãëàñíî (1), (2).
Äëÿ óìåíüøåíèÿ êîëè÷åñòâà ÎÎ (è âû÷èñëåíèé ðàññòîÿíèé äî íèõ) â [51]
äëÿ îäíîãî ÎÎ ñòðîÿò íåñêîëüêî ñôåð ñ ðàçëè÷íûì ðàäèóñîì, à â MVP-tree [51]
èñïîëüçóþò íåñêîëüêî ÎÎ â êàæäîì óçëå, ÷òî óâåëè÷èâàåò êîëè÷åñòâî îáëàñòåé
íà óðîâíå. Â [52] ïðåäëàãàþòñÿ VP-tree ñ îäíèì ÎÎ íà óðîâíå è ñ íåñêîëüêèìè
ÎÎ è âîçìîæíîñòüþ ìíîãîêðàòíîãî ïðèìåíåíèÿ êàæäîãî, à òàêæå àëãîðèòì
çàïðîñà kNN è äèíàìè÷åñêîå êîíñòðóèðîâàíèå.
×òîáû èçáåæàòü îáðàòíîãî ïðîñëåæèâàíèÿ (ñì. ïîäðàçä. 1.5) â [53] ïðåäëî-
æåíî ñôåðè÷åñêîå ðàçáèåíèå íà òðè îáëàñòè ñ îäíèì öåíòðîì è äâóìÿ ðàäèóñà-
ìè, êîòîðûå çàâèñÿò îò ðàäèóñà çàïðîñà. Îáúåêòû äâóõ ñåïàðàáåëüíûõ îáëàñòåé
(áëèæíåé è äàëüíåé îò öåíòðà) ðåêóðñèâíî ïîäâåðãàþòñÿ äàëüíåéøåìó ðàçáèå-
íèþ â òåêóùåì äåðåâå, à îñòàâøèåñÿ ïîñëå åãî ïîñòðîåíèÿ îáúåêòû (èç êîëüöå-
âûõ ñðåäíèõ ÷àñòåé) èñïîëüçóþòñÿ äëÿ êîíñòðóèðîâàíèÿ ñëåäóþùèõ äåðåâüåâ.
Äëÿ çàïðîñà rNN ñ îãðàíè÷åííûì ðàäèóñîì â êàæäîì äåðåâå íå ïðîâîäèòñÿ îá-
ðàòíîãî ïðîñëåæèâàíèÿ, îäíàêî òðåáóåòñÿ îáðàáîòêà ìíîæåñòâà (ëåñà) äåðåâüåâ,
èõ ÷èñëî ìàëî òîëüêî ïðè ìàëîì r.
2.2.2. Ìåòðè÷åñêèå äåðåâüÿ íà îñíîâå îáîáùåííûõ ãèïåðïëîñêîñòåé.
 [48] ñòðîÿò ÈÑ GH-tree èåðàðõè÷åñêèì ðàçáèåíèåì ìíîæåñòâ îáúåêòîâ áàçû
â óçëàõ íà äâà ïîäìíîæåñòâà ïîñðåäñòâîì îáîáùåííûõ ãèïåðïëîñêîñòåé (ñì.
ïîäðàçä. 1.3) ïðè � � 0. Äåðåâî ïîëó÷àåòñÿ íåñáàëàíñèðîâàííîå. Âðåìÿ ïîñòðîå-
íèÿ ñîñòàâëÿåò O N N( log ), à çàòðàòû ïàìÿòè O N( ). Çàïðîñû âûïîëíÿþò ìåòî-
äîì B&B ñ ãèïåðïëîñêîñòíûì èñêëþ÷åíèåì (3).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 173
 ÈÑ BS-tree [54] óñëîâèÿ èñêëþ÷åíèÿ GH-tree óñèëåíû ââåäåíèåì rcov äëÿ
ïîääåðåâüåâ.  ÈÑ V-tree [55] óëó÷øàþò BS-tree çà ñ÷åò èñïîëüçîâàíèÿ äâóõ èëè
òðåõ ÎO â óçëå. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà ÎÎ è âû÷èñëÿåìûõ ðàññòîÿíèé
îäèí èç ÎÎ âûáèðàåòñÿ èç ïðåäøåñòâóþùåãî óðîâíÿ [56].
2.2.3. Ìåòðè÷åñêèå äåðåâüÿ ñ çàïîìèíàíèåì ðàññòîÿíèé è äîïîëíèòåëü-
íûìè îïîðíûìè îáúåêòàìè.  íåêîòîðûõ ìåòðè÷åñêèõ äåðåâüÿõ â äîïîëíåíèå
ê îáëàñòÿì ðàçáèåíèÿ çàïîìèíàþò íåêîòîðûå âû÷èñëåííûå ïðè ïîñòðîåíèè èíäåê-
ñà ðàññòîÿíèÿ (íàïðèìåð, îò ÎÎ äî íåêîòîðûõ îáúåêòîâ áàçû èëè äî äðóãèõ ÎÎ).
Ýòî ïîçâîëÿåò îñóùåñòâëÿòü áîëåå ýôôåêòèâíîå èñêëþ÷åíèå îáëàñòåé è èíäèâè-
äóàëüíûõ îáúåêòîâ.  äîïîëíåíèå ê ñôåðè÷åñêèì îáëàñòÿì MVP-tree [51, 52] çàïî-
ìèíàåò ðàññòîÿíèÿ îáúåêòîâ â ëèñòüÿõ äî èõ ÎÎ âåðõíèõ óðîâíåé.
 ÈÑ M-tree [57] èñïîëüçóþò èåðàðõèþ ñôåðè÷åñêèõ îáëàñòåé âîêðóã íåñêîëü-
êèõ ÎÎ â óçëå (ñ èõ rcov ) è çàïîìèíàþò ðàññòîÿíèÿ ìåæäó ÎÎ (èëè îáúåêòîì áàçû
äëÿ ëèñòîâîãî óçëà) è åãî ðîäèòåëåì. Ïîñòðîåíèå M-tree îñóùåñòâëÿåòñÿ âñòàâêîé
íîâûõ îáúåêòîâ â «ëó÷øåå» ïîääåðåâî (ò.å. áåç èçìåíåíèÿ èëè ñ ìèíèìàëüíûì óâå-
ëè÷åíèåì rcov ). Ïîääåðæèâàåòñÿ ñáàëàíñèðîâàííîñòü äåðåâà: ïðè ïåðåïîëíåíèè
ëèñòà èíèöèèðóåòñÿ ïðîöåññ åãî ðàñùåïëåíèÿ è ïåðåïîñòðîåíèÿ ÷àñòè äåðåâà. Âàðè-
àíòû ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó ñ M-tree ðàññìîòðåíû â [58]. Â ÈÑ
PM-tree [59] îáëàñòü çàäàåòñÿ ïåðåñå÷åíèåì ãèïåðñôåðû è íàáîðà ãèïåðêîëåö ñ öåí-
òðàìè â ãëîáàëüíûõ ÎÎ, ÷òî ïîçâîëÿåò áîëåå ïëîòíî îãðàíè÷èâàòü ïîäìíîæåñòâà
îáúåêòîâ. Äëÿ óìåíüøåíèÿ ïåðåêðûòèÿ îáëàñòåé M-tree (è êîëè÷åñòâà ïîñåùàåìûõ
îáëàñòåé ïðè ïîèñêå) ÈÑ MX-tree [60] èñïîëüçóåò óñëîâíîå ðàçáèåíèå ñ ïîìîùüþ
ñóïåðóçëîâ; êðîìå òîãî, ñîêðàùåíû çàòðàòû íà ïåðåïîñòðîåíèå äåðåâà ïðè ðàñùåï-
ëåíèè, à ìíîæåñòâî îáúåêòîâ â êàæäîì ëèñòå äîïîëíèòåëüíî èíäåêñèðóåòñÿ ñâîèì
VP-tree, ðàñïîëîæåííûì â ñâîáîäíîé îáëàñòè ïàìÿòè MX-tree.
 ÈÑ GNAT [61] îáúåäèíÿþò èäåè GH-tree, MVP-tree, BS-tree, V-tree: èñïîëü-
çóþò èåðàðõèþ îáëàñòåé Äèðèõëå, íåñêîëüêî ÎÎ â óçëå, ñîõðàíåíèå ïðåäâû÷èñëåí-
íûõ ðàññòîÿíèé îò êàæäîé ÎÎ äî ñàìîãî áëèæíåãî è äàëüíåãî îáúåêòà êàæäîé èç m
îáëàñòåé óðîâíÿ. Çà ñ÷åò çàòðàò ïàìÿòè O mN( ) è ñëîæíîñòè ïîñòðîåíèÿ
O mN N( log ) îáåñïå÷èâàåòñÿ óñêîðåíèå ïîèñêà ïî ñðàâíåíèþ ñ VP-tree è GH-tree íà
ðÿäå áàç [61]. Ìîäèôèêàöèÿ GNAT äëÿ ñíèæåíèÿ çàòðàò ïàìÿòè è ïîâûøåíèÿ ñêî-
ðîñòè ïîèñêà ïðåäëîæåíà â [62]. Äèíàìè÷åñêèé âàðèàíò GNAT ïðåäñòàâëåí â [63].
Ïîâûøåíèå ýôôåêòèâíîñòè èñêëþ÷åíèÿ îáúåêòîâ â ðàáîòå [64] îñíîâàíî íà
íàáëþäåíèè, ÷òî âåðîÿòíîñòü èñêëþ÷åíèÿ îáúåêòà óâåëè÷èâàåòñÿ ñ ãëóáèíîé åãî
óðîâíÿ â äåðåâå. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà ÎÎ íà âåðõíèõ óðîâíÿõ ãèïåðïëîñ-
êîñòíûõ äåðåâüåâ (GH-tree, BS-tree) âî âñåõ óçëàõ îäíîãî óðîâíÿ èñïîëüçóþò
îäíó è òó æå ïàðó ÎÎ ñ ðàçíîé áàëàíñèðîâêîé � (3); äëÿ èñêëþ÷åíèÿ îáúåêòîâ
â ëèñòüÿõ ïðèìåíÿþò LAESA ñ ýòèìè æå ãëîáàëüíûìè ÎÎ.
2.2.4. Ëåñà ìåòðè÷åñêèõ äåðåâüåâ. Äëÿ áûñòðîãî ïðèáëèæåííîãî ïîèñêà ïî
ñõîäñòâó âåêòîðîâ óñïåøíî ïðèìåíÿþò ëåñ (ìíîæåñòâî) íåçàâèñèìûõ ðàíäîìè-
çèðîâàííûõ KD-tree [36]. Àíàëîãè÷íàÿ ÈÑ PF ñ èñïîëüçîâàíèåì ìíîæåñòâà ðàí-
äîìèçèðîâàííûõ VP-tree ïðåäëîæåíà â [65]. Äëÿ ïîñòðîåíèÿ êàæäîãî äåðåâà ñëó-
÷àéíî âûáèðàþò ïîäìíîæåñòâî îáúåêòîâ èç ìíîæåñòâà, ïîäëåæàùåãî ðàçáèåíèþ
(âíà÷àëå ýòî âñÿ áàçà), è îäèí ÎÎ èç ïîäìíîæåñòâà. Âû÷èñëÿþò ìåäèàííîå ðàñ-
ñòîÿíèå ïîäìíîæåñòâà îáúåêòîâ îò ÎÎ è èñïîëüçóþò åãî â êà÷åñòâå ðàäèóñà ñôå-
ðû, ïðîöåññ ïîâòîðÿþò, ïîêà ÷èñëî îáúåêòîâ âî ìíîæåñòâàõ íå ñòàíåò ìåíüøå
ïîðîãîâîãî. Ïðè ïîèñêå ïðèáëèæåííûõ kNN â êàæäîì äåðåâå ñïóñêîì èç êîðíÿ
íàõîäÿò ëèñò, îáëàñòè êîòîðîãî ïðèíàäëåæèò îáúåêò-çàïðîñ, è â íåì k áëèæàé-
øèõ îáúåêòîâ-êàíäèäàòîâ (ò.å. áåç îáðàòíîãî ïðîñëåæèâàíèÿ). Èç êàíäèäàòîâ
âñåõ äåðåâüåâ âûáèðàþò k ëó÷øèõ.
Íà íåñêîëüêèõ áàçàõ âåêòîðíûõ äàííûõ ïîêàçàíî ïðåâîñõîäñòâî PF (ïî ïðîöåí-
òó íàéäåííûõ òî÷íûõ kNN) íàä òàêèìè èçâåñòíûìè ÈÑ äëÿ âåêòîðîâ, êàê ëåñ
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
KD-tree è èåðàðõè÷åñêèå K-means [36], îäíàêî ñðàâíåíèå âðåìåíè ïîèñêà íå ïðèâî-
äèòñÿ. Â îïèñàíèè àëãîðèòìà íå èñïîëüçóåòñÿ íåðàâåíñòâî òðåóãîëüíèêà, ïîýòîìó
íå èñêëþ÷åíî åãî ïðèìåíåíèå äëÿ ïîèñêà ïî íåìåòðè÷åñêèì ðàññòîÿíèÿì (ðàçä. 3).
2.3. Ïîèñê ïî ìåòðè÷åñêèì ðàññòîÿíèÿì íà îñíîâå äðåâîâèäíûõ èíäåê-
ñíûõ ñòðóêòóð äëÿ ñêàëÿðíûõ è âåêòîðíûõ äàííûõ. Ðàññòîÿíèÿ îáúåêòà äî
ìíîæåñòâà ÎÎ ïðåäñòàâëÿþò ñîáîé âåùåñòâåííûé âåêòîð (íàáîð îäíîìåðíûõ çíà-
÷åíèé), ñì. ïîäðàçä. 1.4. Äëÿ îäíîìåðíûõ èíäåêñíûõ çíà÷åíèé ñóùåñòâóþò ýôôåê-
òèâíûå ñòðóêòóðû ïîèñêà (ñì. ïîäðàçä. 1.1), à òàêæå èõ àíàëîãè ñ èñïîëüçîâàíèåì
äåðåâüåâ, òàêèå êàê ÈÑ B+tree [66]. Äëÿ ïîèñêà ïî ñõîäñòâó âåùåñòâåííûõ âåêòî-
ðîâ ìàëîé ðàçìåðíîñòè òàêæå ñóùåñòâóþò ýôôåêòèâíûå ÈÑ [14, 25], êîòîðûå
ìîæíî ïðèìåíÿòü äëÿ ïîëó÷åííûõ ñêàëÿðíûõ è âåêòîðíûõ èíäåêñíûõ çíà÷åíèé.
 ðàáîòå [31] êàæäûé êîìïîíåíò ïîëó÷åííûõ âåêòîðîâ èñïîëüçóþò êàê èí-
äåêñíîå çíà÷åíèå îáúåêòîâ â îòäåëüíîì B+tree. Ïðè âûïîëíåíèè çàïðîñà èòîãî-
âûé ñïèñîê êàíäèäàòîâ — ýòî ïåðåñå÷åíèå ìíîæåñòâ îáúåêòîâ-êàíäèäàòîâ îò
êàæäîãî B+tree. Òàêèì îáðàçîì, ïîëó÷àþò âàðèàíò ïîèñêà LAESA ñ ïðèìåíåíè-
åì ëåñà B+tree. Äëÿ èíäåêñèðîâàíèÿ âåêòîðîâ â öåëîì (à íå îòäåëüíûõ
êîìïîíåíòîâ) â [31] èñïîëüçóþò ÈÑ R-tree [25].
 ÈÑ M-index [67] ïðèìåíÿþò îáëàñòè Äèðèõëå (ñì. ïîäðàçä 1.3) ìíîæåñòâà
ãëîáàëüíûõ ÎÎ. Îáëàñòè ñ áîëüøèì êîëè÷åñòâîì îáúåêòîâ ðåêóðñèâíî ðàçáèâà-
þò íà ïîäîáëàñòè ñ èñïîëüçîâàíèåì ÎÎ, íå çàäåéñòâîâàííûõ äëÿ ðàçáèåíèÿ íà
âåðõíèõ óðîâíÿõ. Îáúåêòû ëèñòîâîé îáëàñòè Äèðèõëå äîïîëíèòåëüíî çàêëþ÷åíû
â êîëüöî ñ öåíòðîì â èõ ÎÎ âåðõíåãî óðîâíÿ èåðàðõèè. Äëÿ ïîëó÷åíèÿ îäíîìåð-
íîãî èíäåêñíîãî çíà÷åíèÿ îáúåêòà åãî ðàññòîÿíèå äî áëèæàéøåãî ÎÎ ñóììèðó-
þò ñ èíäåêñíûì çíà÷åíèåì îáëàñòè îáúåêòà íèæíåãî óðîâíÿ èåðàðõèè. Âñå îáú-
åêòû áàçû çàïîìèíàþò â îäíîì B+tree. Ñ îáúåêòîì òàêæå àññîöèèðîâàíû ðàññòî-
ÿíèÿ äî åãî ÎÎ âåðõíèõ óðîâíåé. Òàêèì îáðàçîì, M-index ìîæíî îòíåñòè ê ÈÑ,
ðàññìîòðåííûì â ïîäðàçä. 2.2.3. Áîëåå êîìïàêòíûå îáëàñòè (cut-regions) [68] ïî
àíàëîãèè ñ PM-tree (ñì. ïîäðàçä. 2.2.3) ïîçâîëÿþò ïîâûñèòü ýôôåêòèâíîñòü
èñêëþ÷åíèÿ. Äëÿ áûñòðîãî ïðèáëèæåííîãî ïîèñêà kNN ïðèìåíÿþò
ïðèîðèòåòíóþ î÷åðåäü è ðàííèé îñòàíîâ.
 ÈÑ SPB-tree [69] âåêòîðû ñ êîìïîíåíòàìè, êîòîðûå ÿâëÿþòñÿ ðàññòîÿíèÿ-
ìè äî ãëîáàëüíûõ ÎÎ, ïðåîáðàçóþò â îäíîìåðíûå öåëî÷èñëåííûå èíäåêñíûå
çíà÷åíèÿ ïîñðåäñòâîì çàïîëíÿþùèõ ïðîñòðàíñòâî êðèâûõ (space filling curves,
SFC) [25]. (Áîëüøåé ÷àñòè ïîñëåäîâàòåëüíûõ ÷èñåë íà SFC ñîîòâåòñòâóþò ñîñåä-
íèå ÿ÷åéêè âåêòîðíîãî ïðîñòðàíñòâà.) Ëèñòîâûå óçëû ñîäåðæàò SFC-çíà÷åíèÿ
îáúåêòîâ óçëà, à íåëèñòîâûå — èíôîðìàöèþ îá èåðàðõèè îáëàñòåé. Îáëàñòè ÿâ-
ëÿþòñÿ ìèíèìàëüíûìè îãðàíè÷èâàþùèìè ãèïåðïðÿìîóãîëüíèêàìè (ÌÎÏ) îáú-
åêòîâ ìíîæåñòâà è çàäàþòñÿ ïàðîé âåðøèí (âåêòîðîâ), êîòîðûì ñîîòâåòñòâóþò
SFC-çíà÷åíèÿ. Äëÿ çàïîìèíàíèÿ âñåõ SFC-çíà÷åíèé, à òàêæå àññîöèèðîâàííîé
ñ íèìè èíôîðìàöèè èñïîëüçóþò B+tree. Ïðè âûïîëíåíèè çàïðîñà ïðåîáðàçóþò
îáúåêò-çàïðîñ â âåêòîðíîå ïðåäñòàâëåíèå, îïðåäåëÿþò ãèïåðïðÿìîóãîëüíóþ îá-
ëàñòü çàïðîñà è èñêëþ÷àþò ÌÎÏ-îáëàñòè, íå èìåþùèå ñ íåé ïåðåñå÷åíèÿ. Äàëåå
ïðîâîäÿò âåðèôèêàöèþ îáúåêòîâ-êàíäèäàòîâ îñòàâøèõñÿ îáëàñòåé.
Ðÿä äðóãèõ ìåòîäîâ ôîðìèðîâàíèÿ âåêòîðíûõ ïðåäñòàâëåíèé îáúåêòîâ íà îñíî-
âå èõ ðàññòîÿíèé äî ÎÎ (FastMap, MetricMap, SparseMap, ñì. îáçîð â [22]) íå ãàðàí-
òèðóþò ñæàòèÿ ðàññòîÿíèé èëè âåëè÷èíû èõ èñêàæåíèÿ, ïîýòîìó èõ ìîæíî ïðèìå-
íÿòü òîëüêî äëÿ ïðèáëèæåííîãî ïîèñêà ïî ñõîäñòâó áåç êîëè÷åñòâåííûõ ãàðàíòèé.
2.4. Äåðåâüÿ ñîñåäñòâà äëÿ ïîèñêà ïî ìåòðè÷åñêèì ðàññòîÿíèÿì.  íåêî-
òîðûõ äðåâîâèäíûõ ÈÑ êàæäûé óçåë ñîîòâåòñòâóåò îáúåêòó áàçû è ñâÿçàí ñ ìíî-
æåñòâîì ñâîèõ ñîñåäåé íà ñëåäóþùåì óðîâíå èåðàðõèè. Ïîèñê ïðîâîäèòñÿ ðàñ-
øèðåíèåì ìíîæåñòâà êàíäèäàòîâ îò óçëîâ-ðîäèòåëåé ê óçëàì-ñûíîâüÿì è èñêëþ-
÷åíèåì (ñ èñïîëüçîâàíèåì íåðàâåíñòâà òðåóãîëüíèêà) òåõ èç íèõ, êîòîðûå íå
ìîãóò ïðèâåñòè ê îòâåòó íà çàïðîñ. Íàçîâåì òàêèå ÈÑ äåðåâüÿìè ñîñåäñòâà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 175
Ïðè ïîñòðîåíèè ÈÑ SAT [70] êîðíåì a ÿâëÿåòñÿ ñëó÷àéíûé îáúåêò áàçû.
Åãî ñîñåäè nbr( )a âûáèðàþòñÿ ñëåäóþùåé ýâðèñòèêîé. Îáúåêòû áàçû ñîðòèðóþò
ïî âîçðàñòàíèþ ðàññòîÿíèÿ äî a è ïîñëåäîâàòåëüíî äîáàâëÿþò â (ïåðâîíà÷àëüíî
ïóñòîå) ìíîæåñòâî nbr( )a òå îáúåêòû, êîòîðûå áëèæå ê a , ÷åì ê ëþáîìó îáúåêòó
èç nbr( )a . Îñòàâøèåñÿ îáúåêòû áàçû âêëþ÷àþò â ñïèñîê òîãî îáúåêòà èç nbr ( )a ,
ê êîòîðîìó îíè áëèæå. Îáúåêòû nbr( )a ñòàíîâÿòñÿ óçëàìè ñëåäóþùåãî óðîâíÿ
äåðåâà, è ïðîöåäóðà ïîâòîðÿåòñÿ äëÿ êàæäîãî èç íèõ. Âñå óçëû òàêæå õðàíÿò rcov
îáúåêòîâ ñâîåãî ïîääåðåâà. Çàòðàòû ïàìÿòè ñîñòàâëÿþò O N( ).
Åñëè îáúåêò-çàïðîñ ÿâëÿåòñÿ îáúåêòîì áàçû, òàêàÿ ÈÑ íàõîäèò åãî ïîñëåäîâà-
òåëüíîñòüþ ïåðåõîäîâ íà óçåë-ñîñåä (ñûí), áëèæàéøèé ê îáúåêòó-çàïðîñó. Ïðè âû-
ïîëíåíèè çàïðîñà rNN ïåðåõîäÿò èç êîðíÿ íå íà îäèí, à íà íåêîòîðîå ïîäìíîæåñòâî
åãî ñîñåäåé-ñûíîâåé. Âíà÷àëå ïåðåõîäÿò íà óçåë-ñîñåä, áëèæàéøèé ê îáúåêòó-çà-
ïðîñó, è èñêëþ÷àþò ïî (3) òå óçëû-ñîñåäè êîðíÿ, îáëàñòè êîòîðûõ íå ìîãóò ñîäåð-
æàòü îòâåò íà çàïðîñ. Òàêæå äëÿ èñêëþ÷åíèÿ ïî (1) èñïîëüçóþò rcov óçëîâ-ñîñåäåé.
Äëÿ îñòàâøåãîñÿ ïîäìíîæåñòâà óçëîâ-ñîñåäåé êîðíÿ ðåêóðñèâíî ïîâòîðÿþò âàðèàíò
ïðîöåäóðû èñêëþ÷åíèÿ íà ñëåäóþùåì óðîâíå. Çàïðîñ kNN âûïîëíÿåòñÿ ñ èñïîëü-
çîâàíèåì ïðèîðèòåòíîé î÷åðåäè, âðåìÿ ïîèñêà N N1 1� ( /log log ) .
 äèíàìè÷åñêèõ âàðèàíòàõ SAT äåðåâî ñòðîÿò ïîñëåäîâàòåëüíîé âñòàâêîé
íîâûõ îáúåêòîâ (êàê â ÈÑ DSAT [71]) èëè èõ êëàñòåðîâ [72]. Êîìáèíàöèÿ DSAT
è DLC (ïîäðàçä. 2.5) ïðåäëîæåíà â [73].  ýêñïåðèìåíòàõ DSAT îáåñïå÷èâàþò
áîëåå áûñòðîå ïîñòðîåíèå è ïîèñê, ÷åì SAT. Àíàëèç òàêîãî ïîâåäåíèÿ ïðèâåë
ê ïîÿâëåíèþ ÈÑ DiSAT [74], ãäå â nbr( )a âíà÷àëå äîáàâëÿþò íå áëèæàéøèå,
à äàëüíèå îáúåêòû. Âðåìÿ ïîèñêà DiSAT ïðèáëèçèòåëüíî òàêîå æå, êàê ó LC
(ïîäðàçä. 2.5), îäíàêî ïðè ìåíüøåì âðåìåíè ïîñòðîåíèÿ.
Áûñòðî ðàáîòàþùèì íà ïðàêòèêå ìåòðè÷åñêèì äåðåâîì ñ çàòðàòàìè ïàìÿòè
O N( ) ÿâëÿåòñÿ C-tree [75]. Èåðàðõèÿ óðîâíåé ñîäåðæèò (íàïðèìåð, âûáðàííûé
ñëó÷àéíî) êîðíåâîé îáúåêò íà âåðõíåì óðîâíå è âñå îáúåêòû íà íèæíåì. Îáúåêò,
ïîÿâèâøèéñÿ íà íåêîòîðîì óðîâíå, ïðèíàäëåæèò è âñåì óðîâíÿì íèæå. Êàæäûé
îáúåêò óðîâíÿ i �1 èìååò îäíîãî ðîäèòåëÿ íà ñîñåäíåì âåðõíåì óðîâíå i ñ ðàññòîÿ-
íèåì íå áîëåå 2 i . Äëÿ âñåõ îáúåêòîâ îäíîãî óðîâíÿ ðàññòîÿíèå ïðåâûøàåò 2 i . Òà-
êèì îáðàçîì, ñîñåäè-ñûíîâüÿ óçëîâ óðîâíÿ çàêëþ÷åíû â íåïåðåñåêàþùèåñÿ ñôå-
ðè÷åñêèå îáëàñòè; óðîâåíü êîðíåâîãî óçëà âûáðàí òàêèì, ÷òî åãî îáëàñòü âêëþ÷à-
åò âñå îáúåêòû áàçû. Âîçìîæíî ñòàòè÷åñêîå è äèíàìè÷åñêîå ïîñòðîåíèå C-tree.
Ïðè çàïðîñå NN, ñòàðòóÿ ñ êîðíÿ, íà êàæäîì óðîâíå ïåðåõîäÿò íà óçëû
(â ïîðÿäêå âîçðàñòàíèÿ ðàññòîÿíèé äî îáúåêòà-çàïðîñà x) ñ ðàññòîÿíèåì îò x, íå
ïðåâûøàþùåì 2 i x z�dist ( , ), ãäå z — òåêóùèé NN. Ïîääåðæèâàþòñÿ òàêæå
çàïðîñû kNN, rNN è ïðèáëèæåííûé ïîèñê. Äëÿ çàïðîñà òî÷íîãî NN è äàííûõ ñ êîí-
ñòàíòîé ðàñøèðåíèÿ Ce � 2 (expansion constant), ëîãàðèôì êîòîðîé ñîîòâåòñòâóåò
âíóòðåííåé ðàçìåðíîñòè äàííûõ, â [75] ïîëó÷åíî âðåìÿ O C Ne( log )12 â õóäøåì ñëó-
÷àå. Îäíàêî â [76] ðàññìîòðåíû ïðîáëåìû â äîêàçàòåëüñòâå ýòîãî ðåçóëüòàòà.
2.5. Èíäåêñíûå ñòðóêòóðû ñ íåèåðàðõè÷åñêèì ðàçáèåíèåì íà îáëàñòè.
Íåèåðàðõè÷åñêîé ÈÑ, ãäå ñôåðè÷åñêàÿ îáëàñòü ïåðâîãî ÎÎ ñîäåðæèò m áëèæàé-
øèõ ê ÎÎ îáúåêòîâ áàçû è rcov îáëàñòè, ÿâëÿåòñÿ ÈÑ LC [77]. Ìíîãîêðàòíîå ïî-
âòîðåíèå òàêîãî ðàçáèåíèÿ äëÿ îñòàâøèõñÿ îáúåêòîâ äàåò N m/ ( )�1 îáëàñ-
òåé-êîðçèí. Ñòðóêòóðó LC ìîæíî ðàññìàòðèâàòü êàê íåñáàëàíñèðîâàííîå äåðåâî,
ãäå òîëüêî îäíà èç äâóõ âåòâåé óðîâíÿ ïîäâåðãàåòñÿ äàëüíåéøåìó âåòâëåíèþ.
Ïðè âûïîëíåíèè çàïðîñà ïîñëåäîâàòåëüíî ïðîâåðÿþò óñëîâèå ïåðåñå÷åíèÿ îá-
ëàñòè çàïðîñà è êàæäîé îáëàñòè LC. Åñëè îáëàñòü çàïðîñà ïðèíàäëåæèò îáëàñòè
LC, ïîèñê îñòàíàâëèâàþò. Ýìïèðè÷åñêè LC — îäíà èç ñàìûõ áûñòðûõ ÈÑ òî÷-
íîãî ïîèñêà ñ çàòðàòàìè ïàìÿòè O N( ). Íåäîñòàòêàìè ÿâëÿþòñÿ âðåìÿ ïîñòðîå-
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
íèÿ O N( )2 è íåîáõîäèìîñòü ïîäáîðà m. Äèíàìè÷åñêèé âàðèàíò LC (DLC) ïðè-
âåäåí â [73]. Âàðèàíò LC ñ êîìïàêòíûìè îáëàñòÿìè cut-regions ïðåäëîæåí â [68].
Ñî÷åòàíèå LC ñ ìåòîäàìè ïîäðàçä. 3.1.3. ñì. â [78]. Ïðèáëèæåííûé áûñòðûé ïî-
èñê âûïîëíÿåòñÿ îáõîäîì îáëàñòåé â ïîðÿäêå âîçðàñòàíèÿ ðàññòîÿíèé äî îáúåê-
òà-çàïðîñà ñ ðàííèì îñòàíîâîì [79].
Äèíàìè÷åñêóþ ìíîãîóðîâíåâóþ ÈÑ D-index [80], êàê è LC, ìîæíî ñ÷èòàòü
íåèåðàðõè÷åñêîé. Íà êàæäîì óðîâíå òåêóùóþ îáëàñòü ðàçáèâàþò íà îãðàíè÷åí-
íûå ñåãìåíòàìè ñôåð ñåïàðàáåëüíûå îáëàñòè (ñì. ïîäðàçä. 2.2.1) è îäíó îñòàòî÷-
íóþ îáëàñòü, êîòîðàÿ ñòàíîâèòñÿ òåêóùåé íà ñëåäóþùåì óðîâíå.  îòëè÷èå
îò [53] íà êàæäîì óðîâíå èìååòñÿ íåñêîëüêî ñåïàðàáåëüíûõ îáëàñòåé ñ ðàçëè÷-
íûìè öåíòðàìè, êîòîðûå ÿâëÿþòñÿ êîðçèíàìè. Ïðè çàïðîñå rNN ñ îãðàíè÷åííûì
r ïåðåõîä îñóùåñòâëÿåòñÿ ìàêñèìóì â îäíó îáëàñòü óðîâíÿ (è â îñòàòî÷íóþ îá-
ëàñòü). Âîçìîæåí è ïîèñê ñ áîëüøèì çíà÷åíèåì r. Èíäèâèäóàëüíûå îáúåêòû
èñêëþ÷àþò ïî (4), èñïîëüçóÿ ÎÎ óðîâíÿ.
Íåèåðàðõè÷åñêàÿ ÈÑ RBC [81] ïîçâîëÿåò âûïîëíÿòü êàê òî÷íûé ïîèñê kNN
(ñ àíàëèçîì ñðåäíåãî âðåìåíè), òàê è ïðèáëèæåííûé ïîèñê ñî âðåìåíåì O N( )/1 2
(è ñ àíàëèçîì âåðîÿòíîñòè). Àíàëèç ïðîâåäåí äëÿ äàííûõ ñ èçâåñòíîé Ce . Äëÿ òî÷-
íîãî ïîèñêà êàæäûé (ñëó÷àéíûé) ÎÎ õðàíèò îáúåêòû áàçû èç åãî îáëàñòè Äèðèõ-
ëå è rcov . Çàïðîñ âûïîëíÿåòñÿ èñêëþ÷åíèåì îáëàñòåé âàðèàíòàìè íåðàâåíñòâà òðå-
óãîëüíèêà è ëèíåéíûì ïîèñêîì ñðåäè îñòàâøèõñÿ êàíäèäàòîâ. Äëÿ âåðîÿòíîñòíî-
ãî ïîèñêà ÎÎ õðàíèò çàäàííîå ÷èñëî áëèæàéøèõ ñîñåäåé áàçû (ñïèñêè ìîãóò
ïåðåêðûâàòüñÿ). Ïðè âûïîëíåíèè çàïðîñà íàõîäÿò áëèæàéøèé ÎÎ è èç åãî ñïèñêà
âûáèðàþò k áëèæàéøèõ ñîñåäåé îáúåêòà-çàïðîñà. Íåðàâåíñòâî òðåóãîëüíèêà ïðè-
ìåíÿåòñÿ òîëüêî äëÿ àíàëèçà. Îáå ÈÑ ïîçâîëÿþò ïàðàëëåëüíóþ ðåàëèçàöèþ.
Ðàçëè÷íûå âàðèàíòû íåèåðàðõè÷åñêèõ ÈÑ èç ñåìåéñòâà Singleton [82] êî-
íñòðóèðóþò èç «áëîêîâ», ïðåäñòàâëÿþùèõ ñîáîé îáëàñòè, îãðàíè÷åííûå ñôåðàìè
è ãèïåðïëîñêîñòÿìè, à òàêæå èíäåêñèðîâàíèå îáúåêòîâ ðàññòîÿíèÿìè äî ÎÎ, è èç
ðàçëè÷íûõ êîìáèíàöèé áëîêîâ. Çàäà÷à ñîñòîèò â ñîçäàíèè ÈÑ, îáåñïå÷èâàþùåé
ìèíèìàëüíîå âðåìÿ ïîèñêà. ×åì áîëüøå áëîêîâ â ÈÑ, òåì áîëüøå âðåìåíè çàíè-
ìàåò èñêëþ÷åíèå. Îäíàêî êîëè÷åñòâî îñòàâøèõñÿ îáúåêòîâ-êàíäèäàòîâ óìåíüøà-
åòñÿ è äëÿ èõ âåðèôèêàöèè ëèíåéíûì ïîèñêîì òðåáóåòñÿ ìåíüøå âðåìåíè. Ïðåä-
ïîëàãàåòñÿ, ÷òî èìååòñÿ ãëîáàëüíûé ìèíèìóì çàâèñèìîñòè ñëîæíîñòè ïîèñêà îò
÷èñëà áëîêîâ. Äëÿ áàçû èíêðåìåíòíî, äîáàâëåíèåì áëîêîâ, êîíñòðóèðóþò ÈÑ.
Íàñòðîéêà îïòèìàëüíûõ ïàðàìåòðîâ âûïîëíÿåòñÿ àâòîìàòè÷åñêè, ñòîèìîñòü ïîèñ-
êà îöåíèâàþò ñ èñïîëüçîâàíèåì ìîäåëè ñëîæíîñòè ïîèñêà è ýìïèðè÷åñêè ïîëó-
÷åííîãî âðåìåíè âûïîëíåíèÿ îïåðàöèè. Ñêîðîñòü ïîèñêà ÈÑ ñåìåéñòâà ïðèáëèçè-
òåëüíî òàêàÿ æå èëè â äâà ðàçà áîëüøå, ÷åì ó ñàìûõ áûñòðûõ ñòðóêòóð (LC, EPT,
VP-tree â çàâèñèìîñòè îò áàçû) ïðè ìåíüøåì â 10 ðàç âðåìåíè êîíñòðóèðîâàíèÿ.
2.6. Âûáîð îïîðíûõ îáúåêòîâ. Ýôôåêòèâíîñòü èñêëþ÷åíèÿ (discarding
power) îáúåêòîâ è îáëàñòåé è ñîîòâåòñòâóþùåå óñêîðåíèå ïîèñêà ïî ñõîäñòâó
çíà÷èòåëüíî çàâèñÿò îò èñïîëüçóåìûõ ÎÎ [41, 49, 51, 61]. Ïîñëåäíèå âûáèðàþò
èç îáúåêòîâ áàçû. Äàæå åñëè èìååòñÿ êðèòåðèé îöåíêè êà÷åñòâà ïîäìíîæåñòâà
ÎÎ, êîìáèíàòîðíûé ïåðåáîð âñåõ ïîäìíîæåñòâ äëÿ âûáîðà íàèëó÷øåãî ïðàêòè-
÷åñêè íå îñóùåñòâèì, ïîýòîìó îñòàåòñÿ ðàññ÷èòûâàòü íà ñóáîïòèìàëüíûå æàä-
íûå èíêðåìåíòíûå ýâðèñòèêè.
Âî ìíîãèõ ñëó÷àÿõ äîñòàòî÷íî õîðîøèìè ÎÎ ÿâëÿþòñÿ ñëó÷àéíî âûáðàííûå
îáúåêòû áàçû. Äðóãîé õîðîøåé ýâðèñòèêîé ÿâëÿåòñÿ èñïîëüçîâàíèå â êà÷åñòâå ÎÎ
îáúåêòîâ, óäàëåííûõ îò äðóãèõ îáúåêòîâ áàçû è îò äðóãèõ ÎÎ (âûáðîñû, outliers).
 àëãîðèòìå FFT [83, 84], ñòàðòóÿ ñî ñëó÷àéíîãî îáúåêòà, â êà÷åñòâå ÎÎ èñ-
ïîëüçóþò ñàìûé óäàëåííûé îò íåãî, çàòåì íà êàæäîì øàãå âûáèðàþò îáúåêò,
ìàêñèìàëüíî óäàëåííûé îò ìíîæåñòâà óæå îòîáðàííûõ ÎÎ. Â ðàáîòàõ [51, 52]
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 177
FFT ïðèìåíÿþò äëÿ âûáîðà ÎÎ â VP-tree.  [85] î÷åðåäíîé ÎÎ ìàêñèìèçèðóåò
ñóììó ðàññòîÿíèé äî òåêóùåãî ìíîæåñòâà ÎÎ. Â àëãîðèòìå HOF [31] âûáèðàþò
îáúåêòû áàçû, áëèçêèå ê «ãðàíè÷íûì». Äëÿ ýòîãî âû÷èñëÿþò ðàññòîÿíèå ìåæäó
êàæäûì îáúåêòîì (íå ÎÎ) è âñåìè ÎÎ èç òåêóùåãî ìíîæåñòâà. Âî ìíîæåñòâî
ÎÎ çàíîñÿò îáúåêò, êîòîðûé ìèíèìèçèðóåò ñóììó àáñîëþòíîãî çíà÷åíèÿ
ðàçíîñòåé âû÷èñëåííûõ ðàññòîÿíèé è ðàññòîÿíèÿ ìåæäó ïåðâîé ïàðîé ÎÎ.
 ðàáîòå [85] ýêñïåðèìåíòàëüíî ïîêàçàíî, ÷òî, õîòÿ õîðîøèå ÎÎ ÿâëÿþòñÿ îáú-
åêòàìè-âûáðîñàìè, íå âñå âûáðîñû — õîðîøèå ÎÎ; âûáðîñû ñëåäóåò ðàññìàòðè-
âàòü ëèøü êàê õîðîøèå êàíäèäàòû äëÿ âûáîðà ÎÎ. Â [33] êîìïîíåíòû âåêòîðíîãî
ïðåäñòàâëåíèÿ îáúåêòà áàçû (ñì. ïîäðàçä. 1.4) ïîëó÷àþò êàê ðàññòîÿíèÿ äî îáúåê-
òîâ-âûáðîñîâ, íàéäåííûõ FFT. Èç âåêòîðîâ îáúåêòîâ áàçû ôîðìèðóþò ìàòðèöó, ïî
êîòîðîé íàõîäÿò ãëàâíûå îñè PCA êîâàðèàöèîííîé ìàòðèöû, â êà÷åñòâå ÎÎ âûáè-
ðàþò îáúåêòû-âûáðîñû ñ ìàêñèìàëüíîé ïðîåêöèåé íà ãëàâíûå îñè ÐÑÀ. Â ðàáî-
òå [69] èç îáúåêòîâ-âûáðîñîâ, ïîëó÷åííûõ àëãîðèòìîì HOF [31], èíêðåìåíòíî âû-
áèðàþò â êà÷åñòâå ÎÎ òå, êîòîðûå ìàêñèìèçèðóþò ñðåäíåå çíà÷åíèå îòíîøåíèé
ðàññòîÿíèé L� ìåæäó âåêòîðàìè îáúåêòîâ áàçû è èñõîäíûõ ðàññòîÿíèé.
Êà÷åñòâî äâóõ ìíîæåñòâ ÎÎ îäèíàêîâîé ìîùíîñòè â [85] ïðåäëîæåíî ñðàâ-
íèâàòü ïî âåëè÷èíå ñðåäíåãî ðàññòîÿíèÿ L� ìåæäó âåêòîðíûìè ïðåäñòàâëåíèÿ-
ìè ïîäìíîæåñòâà îáúåêòîâ áàçû â ïðîñòðàíñòâå ðàññòîÿíèé äî ÎÎ èç ñðàâíèâàå-
ìûõ ìíîæåñòâ (÷åì áîëüøå ñðåäíåå ðàññòîÿíèå, òåì áîëüøå âåðîÿòíîñòü èñêëþ-
÷åíèÿ). Èíêðåìåíòíûé àëãîðèòì ïîëó÷åíèÿ çàäàííîãî êîëè÷åñòâà ÎÎ âûáèðàåò
î÷åðåäíîé ÎÎ èç ñëó÷àéíûõ ïîäìíîæåñòâ îáúåêòîâ áàçû êàê îáúåêò î÷åðåäíîãî
ïîäìíîæåñòâà, êîòîðûé ìàêñèìèçèðóåò ñðåäíåå ðàññòîÿíèå.
 ðàáîòå [86] íîâûé îáúåêò âûáèðàåòñÿ îïîðíûì, åñëè åãî ðàññòîÿíèå äî
ëþáîãî èìåþùåãîñÿ ÎÎ áîëüøå, ÷åì çàäàííûé ïðîöåíò ìàêñèìàëüíîãî ðàññòîÿ-
íèÿ ìåæäó îáúåêòàìè áàçû. Ýòî îáåñïå÷èâàåò âîçìîæíîñòü àâòîìàòè÷åñêîãî âû-
áîðà êîëè÷åñòâà ÎÎ è ðàáîòû ñ «ðàñòóùèìè» áàçàìè.  [87] î÷åðåäíûì ÎÎ âû-
áèðàåòñÿ îáúåêò, îáåñïå÷èâàþùèé ìàëóþ (íèæå ïîðîãîâîãî çíà÷åíèÿ) äèñïåð-
ñèþ ðàçíîñòè ðàññòîÿíèé ìåæäó îáúåêòàìè, ñîñåäíèìè â óïîðÿäî÷åííîì ñïèñêå
èõ ðàññòîÿíèé äî ÎÎ. Äëÿ óñòðàíåíèÿ èçáûòî÷íîñòè ÎÎ îñòàâëÿþò òîëüêî òå èç
íèõ, äëÿ êîòîðûõ çíà÷åíèÿ âñåõ ïàðíûõ êîððåëÿöèé âåêòîðîâ ðàññòîÿíèé äî îáú-
åêòîâ áàçû íèæå ïîðîãîâîãî. Â [88] èñïîëüçóþò èíêðåìåíòíûé àëãîðèòì âûáîðà
ÎÎ ñ ìèíèìàëüíîé ñóììàðíîé êîððåëÿöèåé ñ ÎÎ èç óæå îòîáðàííîãî ìíîæåñ-
òâà. Êîððåëÿöèþ äâóõ ÎÎ îöåíèâàþò êàê ñðåäíåå ãåîìåòðè÷åñêîå èëè
ãàðìîíè÷åñêîå äâóõ ñîáñòâåííûõ çíà÷åíèé êîâàðèàöèîííîé ìàòðèöû âåêòîðîâ
ðàññòîÿíèé äî íèõ îáúåêòîâ áàçû.
Íåïîñðåäñòâåííî îöåíèòü èñêëþ÷àþùóþ ñïîñîáíîñòü ÎÎ è èõ ìíîæåñòâ
ïîçâîëÿåò êîëè÷åñòâî èñêëþ÷åííûõ îáúåêòîâ áàçû, ýêñïåðèìåíòàëüíî ïîëó÷åí-
íîå íà çàäàííîì ìíîæåñòâå çàïðîñîâ. Ýòî ìîæíî èñïîëüçîâàòü äëÿ æàäíûõ àëãî-
ðèòìîâ âûáîðà ÎÎ [89–91]. Äëÿ ñíèæåíèÿ âû÷èñëèòåëüíîé ñëîæíîñòè ïðåäëàãà-
þòñÿ ðàçëè÷íûå ñòðàòåãèè ñýìïëèðîâàíèÿ îáúåêòîâ.
Äëÿ îöåíêè âåðîÿòíîñòè èñêëþ÷åíèÿ îáúåêòà áàçû îïîðíûì îáúåêòîì ïðåä-
ëîæåíû ìîäåëè [92, 47], èñïîëüçóþùèå õàðàêòåðèñòèêè ðàñïðåäåëåíèÿ ðàññòîÿ-
íèé ìåæäó îáúåêòàìè áàçû [92], à òàêæå ìåæäó ÎÎ è îáúåêòàìè áàçû [47], êîòî-
ðûå ìîæíî ïîëó÷èòü íà ïîäìíîæåñòâå áàçû. Àíàëèç âåðîÿòíîñòåé èñêëþ÷åíèÿ
ïîêàçàë [92] èõ áîëüøóþ âàðèàáåëüíîñòü äëÿ ðàçëè÷íûõ ÎÎ ìíîæåñòâà. Ïîýòî-
ìó äëÿ ýêîíîìèè ïàìÿòè èìååò ñìûñë õðàíèòü ðàññòîÿíèÿ îáúåêòà íå äî âñåõ
OO, à òîëüêî äî (íåáîëüøîãî) ïîäìíîæåñòâà íàèáîëåå ýôôåêòèâíûõ ÎÎ [92, 47].
Îáû÷íî ýòî ñàìûå äàëüíèå ëèáî ñàìûå áëèæíèå ÎÎ [92, 47].
 EPT [47] (ñì. ïîäðàçä. 2.1) ôîðìèðóþò íåñêîëüêî ãðóïï ÎÎ. Åñëè êîëè÷åñ-
òâà ÎÎ â ãðóïïå è ãðóïï ÎÎ çàäàíû, â êàæäîé ãðóïïå îáúåêòó áàçû íàçíà÷àþò òîò
åäèíñòâåííûé ÎÎ èç êàíäèäàòîâ, ðàññòîÿíèå äî êîòîðîãî áîëüøå äðóãèõ îòëè÷à-
178 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
åòñÿ îò ñðåäíåãî. Ýòî îáåñïå÷èâàåò ïîêðûòèå âñåõ îáúåêòîâ. ×åì áîëüøå ÎÎ
â ãðóïïå, òåì áîëüøå âåðîÿòíîñòü èñêëþ÷åíèÿ. Îöåíêà äèñïåðñèè ðàññòîÿíèé
ìåæäó îáúåêòàìè áàçû, à òàêæå ìåæäó ÎÎ è îáúåêòàìè áàçû ïîçâîëÿåò îöåíèòü
âåðîÿòíîñòü èñêëþ÷åíèÿ.  ñî÷åòàíèè ñ ìîäåëüþ ñòîèìîñòè ïîèñêà ýòî äàåò âîç-
ìîæíîñòü èíêðåìåíòíî âûáðàòü êîëè÷åñòâî ÎÎ â ãðóïïå, ìèíèìèçèðóþùåå âðåìÿ
âûïîëíåíèÿ çàïðîñà (äëÿ çàäàííûõ áàçû, êîëè÷åñòâà ãðóïï ÎÎ, ðàäèóñà çàïðîñà).
2.7. Èñêëþ÷åíèå áåç èñïîëüçîâàíèÿ íåðàâåíñòâà òðåóãîëüíèêà. Âî âñåõ
ðàññìîòðåííûõ ÈÑ èñêëþ÷åíèå îáëàñòåé è îáúåêòîâ âûïîëíÿëîñü âàðèàíòàìè
íåðàâåíñòâà òðåóãîëüíèêà. Êàê óïîìèíàëîñü â ðàçä. 1.3 è 1.4, äëÿ ïîèñêà ïî B&B
ìîæíî èñïîëüçîâàòü è äðóãèå ãðàíèöû.
 [93, 94] ðàññìîòðåíî ñåìåéñòâî ãðàíèö íà îñíîâå íåðàâåíñòâà Ïòîëåìåÿ
dist dist dist dist dist dis( , ) ( , ) ( , ) ( , ) ( , )x y u x y u x u� �� � t ( , )y � .  îáùåì ñëó÷àå èç
íåðàâåíñòâà Ïòîëåìåÿ íå ñëåäóåò íåðàâåíñòâî òðåóãîëüíèêà, è íàîáîðîò.
Äëÿ âåêòîðíûõ ïðîñòðàíñòâ íåðàâåíñòâî Ïòîëåìåÿ ïðèìåíèìî ê ìåòðè÷åñêèì
ðàññòîÿíèÿì êâàäðàòè÷íîé ôîðìû (( ) ( )) /x y A x y� �
T 1 2 , ãäå A — ïîëîæèòåëüíî
îïðåäåëåííàÿ ìàòðèöà, âêëþ÷àÿ åâêëèäîâî. Äëÿ ëþáîãî ìåòðè÷åñêîãî ïðîñòðàí-
ñòâà ñ dist ïðîñòðàíñòâî ñ dist1/2 óäîâëåòâîðÿò íåðàâåíñòâó Ïòîëåìåÿ. Äëÿ ðàññòî-
ÿíèé, ê êîòîðûì ïðèìåíèìî íåðàâåíñòâî Ïòîëåìåÿ, îíî îáåñïå÷èâàåò áîëåå ýô-
ôåêòèâíîå èñêëþ÷åíèå, ÷åì âàðèàíòû íåðàâåíñòâà òðåóãîëüíèêà. Äëÿ ìåòðè÷åñ-
êèõ ïòîëåìè÷åñêèõ ðàññòîÿíèé ñî÷åòàíèå äâóõ èñêëþ÷åíèé äàåò ëó÷øèå
ðåçóëüòàòû, ÷åì èõ îòäåëüíîå èñïîëüçîâàíèå. Ðÿä ðàññòîÿíèé áëèçîê
ê ïòîëåìè÷åñêèì, ÷òî ìîæíî èñïîëüçîâàòü äëÿ ïðèáëèæåííîãî ïîèñêà.  [93]
ðàññìîòðåíû ïòîëåìè÷åñêèå LAESA, PM-tree, M-index.
Ìíîãèå ìåòðè÷åñêèå ïðîñòðàíñòâà èìåþò ñâîéñòâî ÷åòûðåõ òî÷åê
(the four-point property): ëþáûå ÷åòûðå îáúåêòà ìîæíî èçîìåòðè÷åñêè âëîæèòü
â òðåõìåðíîå åâêëèäîâî ïðîñòðàíñòâî [95]. Ýòî ñâîéñòâî ïðèñóùå ëþáîìó ìåò-
ðè÷åñêîìó ïðîñòðàíñòâó, êîòîðîå ìîæíî èçîìåòðè÷åñêè âëîæèòü â ãèëüáåðòîâî
(ìàòðèöà êâàäðàòîâ ðàññòîÿíèé äîëæíà áûòü óñëîâíî îòðèöàòåëüíî ïîëóîïðåäå-
ëåííîé). Ê òàêèì «ñóïåðìåòðè÷åñêèì» [95] ïðîñòðàíñòâàì îòíîñÿòñÿ, íàïðèìåð,
âåêòîðíûå ñ ðàññòîÿíèÿìè Åâêëèäà, Éåíñåíà–Øåííîíà, òðåóãîëüíèêà, êîñèíóñ-
íûì. Âàæíûå ïðîñòðàíñòâà áåç ýòîãî ñâîéñòâà âêëþ÷àþò ìåòðèêè Ìàíõýòòåíà,
×åáûøåâà, Ëåâåíøòåéíà. Îäíàêî äëÿ ëþáîé ìåòðèêè dist ïðîñòðàíñòâî ñ dist1/2
ÿâëÿåòñÿ ñóïåðìåòðè÷åñêèì.
Åñëè ñóïåðìåòðè÷åñêîå ïðîñòðàíñòâî ðàçáèòî íà äâå ÷àñòè ãèïåðïëîñêîñ-
òüþ (ñì. ïîäðàçä.1.3), îáëàñòü o j ìîæíî èñêëþ÷èòü, åñëè (dist 2 ( , )o xj �
� �dist dist2 ( , )) / ( , )o x o o ri i j 2 (ãèëüáåðòîâî èñêëþ÷åíèå). Ýòî óñëîâèå ïîçâîëÿåò
èñêëþ÷àòü áîëüøå îáúåêòîâ, ÷åì (3). Åñëè îáúåêòû èçîáðàçèòü íà ïëîñêîñòè òàê,
÷òîáû èõ ðàññòîÿíèÿ L2 äî ÎÎ ñîâïàäàëè ñ èñõîäíûìè ðàññòîÿíèÿìè dist ( )y oi, ,
dist ( )y o j, , òî ðàññòîÿíèå L2 ìåæäó ëþáîé ïàðîé îáúåêòîâ íà ïëîñêîñòè ÿâëÿåòñÿ
íèæíåé ãðàíèöåé èõ èñõîäíîãî ðàññòîÿíèÿ dist ( , )x y . Â ýêñïåðèìåíòàõ âàðèàíò
GH-tree (ìîíîòîííîå BS-tree) ðàáîòàåò áûñòðåå DiSAT (îáà ñ ãèëüáåðòîâûì èñêëþ-
÷åíèåì). Òðàäèöèîííîå èñêëþ÷åíèå (3) äëÿ ýòèõ äåðåâüåâ ðàáîòàåò ìåäëåííåå.
3. ÈÍÄÅÊÑÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÏÎÈÑÊÀ ÏÎ ÍÅÌÅÒÐÈ×ÅÑÊÈÌ ÐÀÑÑÒÎßÍÈßÌ
 íåêîòîðûõ çàäà÷àõ ïîèñêà ïî ñõîäñòâó (ñì. [32]) ôóíêöèÿ ðàññòîÿíèÿ íå ÿâ-
ëÿåòñÿ ìåòðèêîé: äëÿ íåå íå âûïîëíÿþòñÿ ìåòðè÷åñêèå àêñèîìû, îñîáåííî
âàæíî íåâûïîëíåíèå íåðàâåíñòâà òðåóãîëüíèêà. Ïîýòîìó äëÿ òî÷íîãî ïîèñêà
ïî íåìåòðè÷åñêèì ðàññòîÿíèÿì (èëè ìåðàì íåñõîäñòâà) íåëüçÿ íåïîñðåäñòâåí-
íî èñïîëüçîâàòü ÈÑ, ïðåäñòàâëåííûå â ðàçä. 2. Íå ÿâëÿþòñÿ ìåòðèêàìè ìåðû
ñõîäñòâà, à òàêæå ìíîãèå ïîëó÷åííûå èç íèõ ìåðû íåñõîäñòâà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 179
Ðàññìîòðèì ÈÑ äëÿ óñêîðåíèÿ ïîèñêà ïî íåìåòðè÷åñêèì ðàññòîÿíèÿì.  îò-
ëè÷èå îò ÈÑ, îïèñàííûõ â ðàçä. 2, ìíîãèå ÈÑ, ïðåäñòàâëåííûå â ðàçä. 3, íå îáåñ-
ïå÷èâàþò òî÷íîãî ïîèñêà, íàõîäÿò áëèæàéøèõ ñîñåäåé ñ íåêîòîðîé âåðîÿòíîñ-
òüþ, ÷àñòî áåç åå êîëè÷åñòâåííûõ îöåíîê.  òî æå âðåìÿ íà ïðàêòèêå ðÿä ÈÑ ðà-
áîòàåò áûñòðî è äåìîíñòðèðóåò õîðîøóþ òî÷íîñòü ïîèñêà
3.1. Ïîèñê ñ ïðèìåíåíèåì èíäåêñíûõ ñòðóêòóð äëÿ ìåòðè÷åñêèõ ðàññòî-
ÿíèé è âåêòîðîâ.
3.1.1. Èñïîëüçîâàíèå ÈÑ äëÿ ìåòðè÷åñêèõ ðàññòîÿíèé.  ÈÑ QIC-M-tree
[96] äëÿ ïîèñêà ïî íåìåòðè÷åñêîìó ðàññòîÿíèþ ïðåäëàãàþò êîíñòðóèðîâàòü ÈÑ
äëÿ îãðàíè÷èâàþùåãî åãî ñíèçó ìåòðè÷åñêîãî ðàññòîÿíèÿ, êîòîðîå è èñïîëüçóþò
äëÿ èñêëþ÷åíèÿ îáëàñòåé ÈÑ ïðè âûïîëíåíèè çàïðîñà. Ýòîò ïîäõîä òðåáóåò ðàç-
ðàáîòêè ñæèìàþùåãî ìåòðè÷åñêîãî ðàññòîÿíèÿ äëÿ êàæäîé êîíêðåòíîé íåìåòðè-
êè, ÷òî íå âñåãäà âîçìîæíî.
 ÈÑ LCE [97] áàçó ðàçáèâàþò íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà, äëÿ
êàæäîãî èç êîòîðûõ ââîäèòñÿ ñâîå ìåòðè÷åñêîå ðàññòîÿíèå (ïóòåì ñëîæåíèÿ èñ-
õîäíîãî íåìåòðè÷åñêîãî ðàññòîÿíèÿ ñ âûáðàííîé äëÿ êàæäîãî ïîäìíîæåñòâà
êîíñòàíòîé), ÷òî ïîçâîëÿåò ýôôåêòèâíî èñêëþ÷àòü îáúåêòû êàæäîãî ïîäìíîæåñ-
òâà ñ ïðèìåíåíèåì ìåòðè÷åñêîé ÈÑ (â [97] èñïîëüçóþò ÈÑ íà îñíîâå B+tree).
Îäíàêî LCE òðåáóåò ïîëó÷åíèÿ ìàòðèöû ðàññòîÿíèé ìåæäó îáúåêòàìè áàçû
è ãàðàíòèðóåò òî÷íûé ïîèñê òîëüêî äëÿ îáúåêòîâ-çàïðîñîâ èç áàçû.
Àëãîðèòì TriGen [32] ïîçâîëÿåò èçìåíÿòü ïðîöåíò òðîåê îáúåêòîâ áàçû, äëÿ
êîòîðûõ âûïîëíÿåòñÿ íåðàâåíñòâî òðåóãîëüíèêà. Ïðè óâåëè÷åíèè ýòîãî ïðîöåíòà,
îäíàêî, ðàñòåò âíóòðåííÿÿ ðàçìåðíîñòü áàçû è ñíèæàåòñÿ ñêîðîñòü ïîèñêà, ÷òî
ïðèâîäèò ê íåîáõîäèìîñòè ïîäáîðà ïàðàìåòðîâ äëÿ êîíêðåòíûõ áàç è íå ãàðàíòè-
ðóåò òî÷íîãî ïîèñêà äëÿ íîâûõ îáúåêòîâ.  ÈÑ NM-tree [98] èñïîëüçóþò MT äëÿ
ðàññòîÿíèé, ïðåîáðàçîâàííûõ â ìåòðè÷åñêèå ïîñðåäñòâîì TriGen. Êîìïðîìèññ
ñêîðîñòü/òî÷íîñòü ïîèñêà ðåãóëèðóåòñÿ ïðè âûïîëíåíèè êîíêðåòíûõ çàïðîñîâ.
Äëÿ âûïîëíåíèÿ çàïðîñà rNN ïî íåìåòðè÷åñêîé äèâåðãåíöèè Áðåãìàíà
â [20] èñïîëüçîâàí âàðèàíò ñôåðè÷åñêîãî äåðåâà è ìåòîä B&B ñ ïðåäëîæåííûìè
óñëîâèÿìè âêëþ÷åíèÿ è ïåðåñå÷åíèÿ ñôåðè÷åñêèõ îáëàñòåé Áðåãìàíà.
Äëÿ ïîèñêà (òî÷íîãî è ïðèáëèæåííîãî) ïî ìàêñèìàëüíîìó çíà÷åíèþ ñõîä-
ñòâà, çàäàâàåìîãî ÿäåðíîé ôóíêöèåé, çíà÷åíèÿ êîòîðîé ñîîòâåòñòâóþò ñêàëÿðíî-
ìó ïðîèçâåäåíèþ âåêòîðíûõ ïðåäñòàâëåíèé îáúåêòîâ â íåêîòîðîì ãèëüáåðòîâîì
ïðîñòðàíñòâå, â [99] èíäóöèðîâàííîå ÿäåðíîé ôóíêöèåé ðàññòîÿíèå èñïîëüçóþò
äëÿ êîíñòðóèðîâàíèÿ C-tree (ñì. ïîäðàçä. 2.4). Äëÿ ïîèñêà ïðèìåíÿþò ìåòîä
B&B ñ ïðåäëîæåííîé âåðõíåé ãðàíèöåé çíà÷åíèÿ ÿäðà ìåæäó îáúåêòîì-çàïðî-
ñîì è ëþáûì îáúåêòîì â ïîääåðåâå.
3.1.2. Èñïîëüçîâàíèå ÈÑ äëÿ âåêòîðîâ. Ìåòîäû ôîðìèðîâàíèÿ âåêòîðíûõ
ïðåäñòàâëåíèé îáúåêòîâ íà îñíîâå èõ ðàññòîÿíèé äî ÎÎ ìîæíî ïðèìåíÿòü ê íå-
ìåòðè÷åñêèì ðàññòîÿíèÿì, ÷òî ïîçâîëÿåò èñïîëüçîâàòü ÈÑ, ïðåäíàçíà÷åííûå äëÿ
ïîèñêà âåêòîðîâ [25, 14]. Îäíàêî äëÿ òàêîãî ïðåîáðàçîâàíèÿ (ñì. ïîäðàçä. 1.4)
â ýòîì ñëó÷àå óæå íå ãàðàíòèðóåòñÿ ñæàòèÿ ðàññòîÿíèé. Ðÿä äðóãèõ ìåòîäîâ ôîð-
ìèðîâàíèÿ âåêòîðíûõ ïðåäñòàâëåíèé îáúåêòîâ íà îñíîâå èõ ðàññòîÿíèé äî ÎÎ
(FastMap, MetricMap, SparseMap [22]) íå ãàðàíòèðóþò íå òîëüêî ñæàòèÿ ðàññòîÿ-
íèé, íî è çíà÷åíèé èõ èñêàæåíèÿ. Ýòî òàêæå îòíîñèòñÿ ê àëãîðèòìàì ôîðìèðîâà-
íèÿ âåêòîðíûõ ïðåäñòàâëåíèé ñ ïðèìåíåíèåì îáó÷åíèÿ (cì. ññûëêè â [32]). Ïîý-
òîìó êà÷åñòâî ðåçóëüòàòîâ ïîèñêà ïî ïîëó÷åííûì âåêòîðàì ìîæíî îöåíèòü òîëü-
êî ýêñïåðèìåíòàëüíî.
Äëÿ íåêîòîðûõ êîíêðåòíûõ íåìåòðè÷åñêèõ ðàññòîÿíèé/ñõîäñòâ ìîæíî ïîëó-
÷èòü ïëîòíûå ãðàíèöû èñõîäíûõ ðàññòîÿíèé ÷åðåç ðàññòîÿíèÿ ìåæäó ïîëó÷åí-
íûìè âåêòîðàìè. Íàïðèìåð, äëÿ ïîèñêà ïî íåìåòðè÷åñêîìó ðàññòîÿíèþ dynamic
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
time warping ìåæäó âðåìåííûìè ðÿäàìè â [100] ôîðìèðóþò âåêòîðíûå ïðåäñòàâ-
ëåíèÿ è èñïîëüçóþò ïëîòíóþ ãðàíèöó èñõîäíîãî ðàññòîÿíèÿ äëÿ ýôôåêòèâíîãî
òî÷íîãî ïîèñêà â ÈÑ äëÿ âåêòîðîâ íà îñíîâå R-tree. Èñïîëüçîâàíèå âåêòîðíûõ
ÈÑ äëÿ ïîèñêà ïî äèâåðãåíöèè Áðåãìàíà ñì. â [101, 102].
3.1.3. Ïðåäñòàâëåíèÿ íà îñíîâå áëèæàéøèõ îïîðíûõ îáúåêòîâ. Â ðàáî-
òàõ [103–109] ôîðìèðóþò «ñèãíàòóðû» îáúåêòîâ íà îñíîâå èíôîðìàöèè îá èõ áëè-
æàéøèõ ÎÎ. Ðàññòîÿíèÿ/cõîäñòâà ñèãíàòóð â íåêîòîðîé ñòåïåíè ñîîòâåòñòâóþò èñ-
õîäíûì ðàññòîÿíèÿì/cõîäñòâàì îáúåêòîâ. Ïðè âûïîëíåíèè çàïðîñà ïîëó÷àþò ñèã-
íàòóðó îáúåêòà-çàïðîñà è ðàññìàòðèâàþò â êà÷åñòâå êàíäèäàòîâ òîëüêî òå îáúåêòû
áàçû, ñèãíàòóðû êîòîðûõ áëèçêè ê ñèãíàòóðå îáúåêòà-çàïðîñà. Óñêîðåíèå ïîèñêà
äîñòèãàåòñÿ çà ñ÷åò áîëåå ýôôåêòèâíîãî ïîèñêà ñõîäíûõ ñèãíàòóð, ÷åì ëèíåéíûé
ïîèñê ïî èñõîäíûì ìåðàì ðàññòîÿíèÿ/cõîäñòâà îáúåêòîâ. Ñèãíàòóðà îáúåêòà ìîæåò
âêëþ÷àòü ðàçëè÷íóþ èíôîðìàöèþ (íàïðèìåð, ìíîæåñòâî áëèæàéøèõ ÎÎ îáúåêòà,
ðàíãè èõ ñõîäñòâ, çíà÷åíèÿ ñõîäñòâ è äð.). Ïî-ðàçíîìó ìîæíî îïðåäåëÿòü ìåðû ñõî-
äñòâà ìåæäó ñèãíàòóðàìè, èõ ïàðàìåòðû è àëãîðèòìû îáðàáîòêè ñèãíàòóð äëÿ âû-
ïîëíåíèÿ çàïðîñîâ, âêëþ÷àÿ ïðèìåíåíèå ÈÑ äëÿ ïîèñêà ñõîäíûõ âåêòîðîâ è ìíî-
æåñòâ. Ïîèñê íå èìååò ãàðàíòèé òî÷íîñòè, íå èñïîëüçóåò â ÿâíîì âèäå íåðàâåíñòâà
òðåóãîëüíèêà äëÿ èñõîäíûõ ðàññòîÿíèé è åãî ìîæíî ïðèìåíÿòü êàê äëÿ ìåòðè÷åñ-
êèõ, òàê è äëÿ íåìåòðè÷åñêèõ ðàññòîÿíèé/ñõîäñòâ [110]. Àëãîðèòìû ïîêàçûâàþò õî-
ðîøèå ðåçóëüòàòû â ýêñïåðèìåíòàõ è îáîáùåíû â [109].
 ðàáîòàõ [103, 104] ñèãíàòóðà îáúåêòà y ÿâëÿåòñÿ âåêòîðîì, êîìïîíåíòó
âåêòîðà ñîîòâåòñòâóåò OO èç ôèêñèðîâàííîãî ìíîæåñòâà, çíà÷åíèå êîìïîíåíòà
ðàâíî íîìåðó ÎÎ â ñïèñêå ÎÎ, îòñîðòèðîâàííîì ïî âåëè÷èíå ðàññòîÿíèÿ îò y.
Ðàññòîÿíèå ìåæäó ñèãíàòóðàìè îïðåäåëÿåòñÿ ïî L1 èëè L2è èñïîëüçóåòñÿ äëÿ
îòáîðà êàíäèäàòîâ ëèíåéíûì ïîèñêîì [103].
Áèíàðíûé âåêòîð â [105] ïîëó÷àþò ñðàâíåíèåì ñ ïîðîãîì ðàçíîñòè çíà÷åíèÿ
è íîìåðà êîìïîíåíòà âåêòîðà. Äàëåå âûïîëíÿþò ëèíåéíûé ïîèñê ïî ðàññòîÿíèþ
Õýììèíãà ìåæäó áèíàðíûìè âåêòîðàìè èëè ïðèìåíÿþò ïîèñê LSH (ïîäðàçä. 3.4).
 ÈÑ MIF [103] äëÿ y çàïîìèíàþò òîëüêî K áëèæàéøèõ ÎÎ. Äëÿ ñðàâíåíèÿ
ñèãíàòóð èñïîëüçóþò ìîäèôèêàöèþ ðàññòîÿíèÿ L1, ãäå ïðè îòñóòñòâèè ñîîòâåòñòâó-
þùåãî ÎÎ ê çíà÷åíèþ ðàññòîÿíèÿ äîáàâëÿåòñÿ øòðàô. Óñêîðåíèÿ ñðàâíåíèÿ ñèãíà-
òóð çàïðîñà è îáúåêòîâ áàçû äîñòèãàþò ïðèìåíåíèåì îáðàòíîãî èíäåêñà, â êîòîðîì
äëÿ êàæäîãî ÎÎ çàïîìèíàþò ñïèñîê îáúåêòîâ áàçû ñ èõ ðàíãàìè. Èíäåêñèðîâàíèå
ïðåôèêñíûì äåðåâîì ïðåäëîæåíî â [107]. Îöåíèâàòü ñõîäñòâî îáúåêòîâ ïî ïðîöåí-
òó èõ îáùèõ áëèæàéøèõ ÎÎ (áåç ó÷åòà èõ ðàíãà) ïðåäëîæåíî â àëãîðèòìå NAPP
[108]. Ïîèñê óñêîðÿþò çà ñ÷åò ïðèìåíåíèÿ ýôôåêòèâíîãî îáðàòíîãî èíäåêñà.  [109]
ïðåäñòàâëåíû è äðóãèå âàðèàíòû ðåàëèçàöèè ýòîãî ïîäõîäà.
3.2. Ïîèñê íà îñíîâå ñðàâíåíèé. Ýòîò ïîäõîä, òàêæå èçâåñòíûé êàê «êîìáè-
íàòîðíûé» [111], èñïîëüçóåò ïðè ïîèñêå ïî ñõîäñòâó òîëüêî èíôîðìàöèþ î òîì,
êàêîé èç äâóõ îáúåêòîâ áëèæå ê òðåòüåìó, ÷òî ïîçâîëÿåò ðàíæèðîâàòü îáúåêòû.
Íåðàâåíñòâî òðåóãîëüíèêà íå èñïîëüçóåòñÿ. Ïîäõîä ìîæíî ïðèìåíÿòü êàê äëÿ
ìåòðè÷åñêèõ, òàê è äëÿ íåìåòðè÷åñêèõ ðàññòîÿíèé/ñõîäñòâ. Îòìåòèì, ÷òî ìíîãèå
ñèãíàòóðû (ñì. ïîäðàçä. 3.1.3) òîæå ôîðìèðóþòñÿ íà îñíîâå ðàíæèðîâàíèÿ.
 ðàáîòå [111] ïðåäëîæåí àíàëîã íåðàâåíñòâà òðåóãîëüíèêà äëÿ ðàíãîâ
ñõîäñòâ ñ èñïîëüçîâàíèåì êîíñòàíòû áåñïîðÿäêà Cd (disorder constant), log Cd �1
ÿâëÿåòñÿ ðàçíîâèäíîñòüþ âíóòðåííåé ðàçìåðíîñòè: rank ranky d zx C x( ) ( ( )� �
� rank z y( )), ãäå rank y x( ) — ïîëîæåíèå îáúåêòà x â ñïèñêå îáúåêòîâ áàçû,
îòñîðòèðîâàííûõ ïî ñõîäñòâó ñ y.
Ïðàêòè÷åñêèé àëãîðèòì RanWalk [111] äëÿ ïîèñêà NN èñïîëüçóåò ñëó÷àé-
íûå áëóæäàíèÿ. Ïðè ïîñòðîåíèè äëÿ êàæäîãî îáúåêòà áàçû ñîðòèðóþò ïî ñõîä-
ñòâó ñ íèì âñå îñòàëüíûå îáúåêòû è çàïîìèíàþò. Ïðè âûïîëíåíèè çàïðîñà, ñòàð-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 181
òóÿ ñî ñëó÷àéíîãî îáúåêòà, ñëó÷àéíî âûáèðàþò 3 1C Nd (log log )� îáúåêòîâ èç
åãî «îêðåñòíîñòè» ñ çàäàííûì ÷èñëîì îáúåêòîâ. Âû÷èñëÿþò èõ ðàññòîÿíèÿ äî
îáúåêòà-çàïðîñà è ïåðåõîäÿò íà áëèæàéøèé. Ïîâòîðÿþò òàêîé øàã log N ðàç
ñ óìåíüøåíèåì îêðåñòíîñòè íà êàæäîì øàãå è îêàçûâàþòñÿ â îáúåêòå y. Åñëè
ðàíã îáúåêòà-çàïðîñà ïî îòíîøåíèþ ê y áîëüøå Cd , ïðîöåäóðó ïîâòîðÿþò, èíà-
÷å âûïîëíÿþò ïîèñê â îêðåñòíîñòè y ñ ÷èñëîì îáúåêòîâ C
d
2 . Òî÷íûé NN âîçâðà-
ùàåòñÿ RanWalk çà ñðåäíåå âðåìÿ O C N N Cd d
( log log log )�
2 , îäíàêî òðåáóåò
êâàäðàòè÷íûõ âðåìåíè ïîñòðîåíèÿ è ïàìÿòè.
Íèæíÿÿ ãðàíèöà ñðåäíåãî âðåìåíè ïîèñêà NN â ðàíäîìèçèðîâàííûõ àëãî-
ðèòìàõ êîìáèíàòîðíîãî ïîäõîäà è èåðàðõè÷åñêàÿ ÈÑ ñ èñïîëüçîâàíèåì ñýìïëè-
ðîâàíèÿ äëÿ ïîèñêà NN è rNN ïðèâåäåíû â [113]. Ïî÷òè ëèíåéíûì âðåìåíåì ïî-
ñòðîåíèÿ è çàòðàòàìè ïàìÿòè è ïî÷òè ëîãàðèôìè÷åñêèì âðåìåíåì çàïðîñà òî÷íî-
ãî NN îòëè÷àþòñÿ äåòåðìèíèðîâàííûå combinatorial nets [112], ãäå ñòðîèòñÿ
èåðàðõè÷åñêàÿ ñòðóêòóðà ïîêðûòèé îáúåêòîâ ñ ýêñïîíåíöèàëüíî óáûâàþùèì
ðàäèóñîì. Îäíàêî àëãîðèòìû [112, 113] íå ðåàëèçîâàíû.
Ïðàêòè÷åñêîé ÈÑ íà îñíîâå ñðàâíåíèé ÿâëÿåòñÿ SASH [114]. Ïðè êîíñòðóè-
ðîâàíèè ñëó÷àéíî âûáèðàåòñÿ ïîëîâèíà îáúåêòîâ òåêóùåãî ìíîæåñòâà (âíà÷àëå
âñå îáúåêòû áàçû), êîòîðûå ñòàíîâÿòñÿ óçëàìè íà òåêóùåì óðîâíå èåðàðõèè.
Ïðîöåäóðà ïîâòîðÿåòñÿ, ïîêà íå îñòàíåòñÿ îäèí êîðíåâîé îáúåêò. Ñõîäíûå îáú-
åêòû ñîñåäíèõ óðîâíåé ñîåäèíÿþò ðåáðàìè. Êàæäûé óçåë (êðîìå êîðíÿ) ìîæåò
ñîåäèíÿòüñÿ ñ íåñêîëüêèìè ðîäèòåëÿìè, ïîýòîìó SASH ÿâëÿåòñÿ ãðàôîì, à íå äå-
ðåâîì. Äëÿ ïîèñêà kNN, ñòàðòóÿ ñ êîðíÿ, ïåðåõîäÿò ïî ðåáðàì íà áëèæàéøèå
ê îáúåêòó-çàïðîñó óçëû ñëåäóþùåãî óðîâíÿ (êîëè÷åñòâî óçëîâ îïðåäåëÿåòñÿ êâî-
òîé óðîâíÿ). Ýòè óçëû ÿâëÿþòñÿ êàíäèäàòàìè, ñðåäè êîòîðûõ âûáèðàþò k áëè-
æàéøèõ ê çàïðîñó îáúåêòîâ.  îòëè÷èå îò äåðåâüåâ ñîñåäñòâà (ñì. ïîäðàçä. 2.4)
íåðàâåíñòâî òðåóãîëüíèêà íå èñïîëüçóåòñÿ. Íàõîæäåíèå òî÷íûõ kNN íå
ãàðàíòèðóåòñÿ, íî ÷àñòî íàáëþäàåòñÿ íà ïðàêòèêå.
Ê êîìáèíàòîðíîìó ïîäõîäó îòíîñèòñÿ ïðàêòè÷åñêèé àëãîðèòì RC-tree [115] ñî
ñòðóêòóðîé, ïîäîáíîé C-tree è SASH. Ïðè ïîèñêå ïåðåõîä îñóùåñòâëÿåòñÿ íà óçëû,
íàèáîëåå ñõîäíûå ñ îáúåêòîì-çàïðîñîì (ïî ðàíãó), ÷èñëî êîòîðûõ çàäàåòñÿ êâîòîé
óðîâíÿ. Àíàëèç ïîêàçûâàåò, ÷òî RC-tree ñ âûñîêîé âåðîÿòíîñòüþ âîçâðàùàåò òî÷íûå
kNN ïðè âðåìåíè âûïîëíåíèÿ çàïðîñà ñ ìåíüøåé ñòåïåíüþ ïîëèíîìèàëüíîé çàâè-
ñèìîñòè îò Ce , ÷åì â CT, è ñóáëèíåéíîé çàâèñèìîñòüþ îò N . Ýêñïåðèìåíòàëüíî
RC-tree áûñòðåå C-tree è SASH íà áîëüøèíñòâå èññëåäîâàííûõ áàç. Ê ïîèñêó íà
îñíîâå ñðàâíåíèé îòíîñÿòñÿ òàêæå ÈÑ, îïèñàííûå â ïîäðàçä. 3.3.
3.3. Èíäåêñíûå ñòðóêòóðû íà îñíîâå ãðàôîâ ñîñåäñòâà. Â ãðàôå ñîñåäñòâà
(proximity graph èëè neighborhood graph) îáúåêòû áàçû ñîîòâåòñòâóþò óçëàì,
à îðèåíòèðîâàííûå ðåáðà íàïðàâëåíû ê «ñîñåäíèì» (â ðàçíîì ñìûñëå) îáúåêòàì.
Àëãîðèòì æàäíîãî ïîèñêà ñòàðòóåò ñî ñëó÷àéíîãî óçëà è ðàíæèðóåò åãî ñîñåäåé
îòíîñèòåëüíî îáúåêòà-çàïðîñà x. Åñëè òåêóùèé óçåë áëèæå ê x, ÷åì âñå ñîñåäè
óçëà («ëîêàëüíûé ìèíèìóì»), òî îí è ÿâëÿåòñÿ îòâåòîì íà çàïðîñ. Â ïðîòèâíîì
ñëó÷àå ïåðåõîäÿò ê áëèæàéøåìó ê x ñîñåäó [70, 13].
Ïðîñòåéøèì ãðàôîì, äëÿ êîòîðîãî òàêîé àëãîðèòì æàäíîãî ïîèñêà íàõîäèò
òî÷íîãî áëèæàéøåãî ñîñåäà, ÿâëÿåòñÿ ïîëíîñâÿçíûé ãðàô, îäíàêî â êàæäîì óçëå
óæå òðåáóåòñÿ ëèíåéíûé ïîèñê ïî âñåé áàçå. Äëÿ âåêòîðíûõ ïðîñòðàíñòâ ãðàô
ñ ìèíèìàëüíûì ÷èñëîì ðåáåð, ïîçâîëÿþùèé æàäíî íàõîäèòü NN, — ýòî ãðàô
Äåëîíå (Delaunay), íî äëÿ îáùèõ ìåòðè÷åñêèõ ðàññòîÿíèé åãî íåëüçÿ ïîñòðîèòü
ïî ìàòðèöå ðàññòîÿíèé ìåæäó îáúåêòàìè [70]. Îäíàêî äëÿ ïîèñêà ïðèáëèæåííî-
ãî NN íå òðåáóåòñÿ òî÷íîãî ãðàôà Äåëîíå, ïîýòîìó íà ïðàêòèêå èñïîëüçóþò
ãðàôû, ïîäãðàôû êîòîðûõ ÿâëÿþòñÿ åãî àïïðîêñèìàöèåé.
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Àëãîðèòì äëÿ ñîåäèíåíèÿ êàæäîãî îáúåêòà ñ ñîñåäÿìè â [116] òàêîé æå, êàê äëÿ
êîðíÿ SAT ([70] è ñì. ïîäðàçä. 2.4), è æàäíûé ïîèñê íàõîäèò îáúåêò áàçû, ñîâïàäà-
þùèé ñ îáúåêòîì-çàïðîñîì x ïðè ñòàðòå èç ïðîèçâîëüíîãî óçëà. Äëÿ x íå èç áàçû
ýòîãî íå ãàðàíòèðóåòñÿ è ïðèìåíÿþò ïîèñê best-first.  [117] â êà÷åñòâå àïïðîêñèìà-
öèè ãðàôà Äåëîíå ïðåäëîæåíî èñïîëüçîâàòü ãðàô KNN, â êîòîðîì êàæäûé óçåë
èìååò îðèåíòèðîâàííûå ñâÿçè ñ K áëèæàéøèìè ñîñåäÿìè (K k
â îáùåì ñëó÷àå).
×åì ìåíüøå ñòåïåíü óçëîâ K, òåì ìåíüøå ÷èñëî ïîñåùàåìûõ íà êàæäîì øàãå óçëîâ,
îäíàêî óìåíüøàåòñÿ è âåðîÿòíîñòü íàõîæäåíèÿ òî÷íîãî NN. Óñèëèÿ ïî ðàçâèòèþ
ýòîãî ïîäõîäà (ïîäðàçä. 3.3.1 è 3.3.2) íàïðàâëåíû íà ïîâûøåíèå ñêîðîñòè ïîèñêà
è êà÷åñòâà íàéäåííûõ ñîñåäåé, óìåíüøåíèå ñëîæíîñòè ïîñòðîåíèÿ ãðàôà KNN.
3.3.1. Ïîèñê áëèæàéøèõ ñîñåäåé. Äëÿ òî÷íûõ çàïðîñîâ rNN è kNN â [118]
ïðèìåíÿþò ìîäèôèêàöèþ ãðàôà KNN, â êîòîðîé çàïîìíåíû ðàññòîÿíèÿ íà ðåá-
ðàõ, à òàêæå rcov óçëîâ.  ñî÷åòàíèè ñ íåðàâåíñòâîì òðåóãîëüíèêà ýòî èñïîëüçó-
åòñÿ äëÿ èñêëþ÷åíèÿ îáúåêòîâ è âûáîðà äëÿ îáðàáîòêè íåïîñåùåííûõ óçëîâ.
Óñêîðåíèå äîñòèãàåòñÿ äëÿ äàííûõ ìàëîé ðàçìåðíîñòè.
 äðóãèõ ðàáîòàõ íå ãàðàíòèðóåòñÿ íàõîæäåíèÿ òî÷íûõ kNN.  [119] äëÿ ïîèñ-
êà îäíîãî NN ïðèìåíÿþò îäíîêðàòíûé ñïóñê æàäíîãî àëãîðèòìà â ëîêàëüíûé ìè-
íèìóì, ñòàðòóÿ ñî ñëó÷àéíî âûáðàííîãî óçëà; ðàññòîÿíèÿ âû÷èñëÿþò äî E K� ñîñå-
äåé óçëà â ãðàôå (K �1000). Äëÿ ïîèñêà kNN ïðåäóñìîòðåí ðåñòàðò èç íåñêîëüêèõ
ñëó÷àéíûõ óçëîâ, îñòàíîâ ïîèñêà — ïî çàäàííîìó ÷èñëó æàäíûõ ïåðåõîäîâ íà áëè-
æàéøèé ê îáúåêòó-çàïðîñó x óçåë èç E ñîñåäåé òåêóùåãî óçëà (áåç ïðîâåðêè íà ëî-
êàëüíûé ìèíèìóì). Íåñêîëüêî ðåñòàðòîâ ïðèìåíÿþò â [117, 120, 121]; îáúåêòû, ïî-
ëó÷åííûå æàäíûì ïîèñêîì ëîêàëüíîãî ìèíèìóìà îò âñåõ ðåñòàðòîâ, ñîðòèðóþò
è âûáèðàþò k íàèëó÷øèõ. Â [121] îñòàíîâ âûïîëíÿþò ïðè îòñóòñòâèè èçìåíåíèÿ
â ñïèñêå òåêóùèõ kNN; ÷òîáû èçáåæàòü äóáëèðîâàíèÿ, èñïîëüçóþò åäèíûé ñïè-
ñîê íåïîñåùåííûõ óçëîâ äëÿ âñåõ ðåñòàðòîâ.
Ìíîãèå àëãîðèòìû ïîèñêà ïî ãðàôàì ñîñåäñòâà èñïîëüçóþò äëÿ îáõîäà ïðè-
îðèòåòíóþ î÷åðåäü íåïîñåùåííûõ óçëîâ, óïîðÿäî÷åííûõ ïî ðàññòîÿíèþ äî îáú-
åêòà-çàïðîñà (ñì. ïîäðàçä. 1.5). Íà êàæäîì øàãå èçâëåêàþò ëó÷øèé óçåë è ïîìå-
ùàþò â î÷åðåäü åãî íåïîñåùåííûõ ñîñåäåé ïî ãðàôó. Âìåñòî îñòàíîâà â ëîêàëü-
íîì ìèíèìóìå èç î÷åðåäè èçâëåêàþò ñëåäóþùèé óçåë è èññëåäóþò åãî ñîñåäåé
(àíàëîã îáðàòíîãî ïðîñëåæèâàíèÿ).
 î÷åðåäü çàíîñÿò óçëû, ïîëó÷àåìûå îáõîäîì ãðàôà èç îäíîãî óçëà (íàïðè-
ìåð, [122]) èëè îò íåñêîëüêèõ ðåñòàðòîâ (íàïðèìåð, [117]).  [117] â î÷åðåäü çà-
íîñÿò óçëû èç «ðàñøèðåííîé îêðåñòíîñòè» òåêóùåãî óçëà, ò.å. ñâÿçàííûå ñ íèì
÷åðåç óçëû, ðàññòîÿíèå êîòîðûõ äî îáúåêòà-çàïðîñà íå ïðåâûøàåò ïîðîãîâîãî.
Îñòàíîâ ïîèñêà âûïîëíÿþò ïî êîëè÷åñòâó âû÷èñëåííûõ ðàññòîÿíèé [122] èëè ïî
ñîîòíîøåíèþ ðàññòîÿíèé äî áëèæàéøåãî óçëà è äî òåêóùåãî NN [117].
3.3.2. Êîíñòðóèðîâàíèå ãðàôîâ KNN è èõ àïïðîêñèìàöèé. Êîíñòðóèðîâà-
íèå òî÷íîãî ãðàôà KNN â îáùåì ñëó÷àå èìååò ñëîæíîñòü O N( )2 , ÷òî íåïðèåì-
ëåìî íà ïðàêòèêå. Ïðè ìåòðè÷åñêèõ ðàññòîÿíèÿõ óñêîðåíèÿ ìîæíî äîñòè÷ü ïðè-
ìåíåíèåì ÈÑ äëÿ òî÷íîãî ïîèñêà (ñì. ðàçä. 2).  ñî÷åòàíèè ñ îïòèìèçàöèåé çà
ñ÷åò ñîâìåñòíîãî âûïîëíåíèÿ N çàïðîñîâ è èñïîëüçîâàíèåì óæå ïîñòðîåííîé
÷àñòè ãðàôà äëÿ ïîëó÷åíèÿ ãðàíèö íà íåêîòîðûå ðàññòîÿíèÿ ýòî ïîçâîëÿåò ñíè-
çèòü ýìïèðè÷åñêóþ ñëîæíîñòü êîíñòðóèðîâàíèÿ, îñîáåííî äëÿ äàííûõ íåâûñî-
êîé ðàçìåðíîñòè [123] (äî O N( ).11 ïðè D � 4 è äî O N( ).1 96 ïðè D � 24).
Ãðàô ïðèáëèæåííûõ KNN ìîæíî ñêîíñòðóèðîâàòü ýôôåêòèâíåå êàê áûñ-
òðûì ïîèñêîì ïðèáëèæåííûõ KNN, òàê è áîëåå ïðîñòûìè ñðåäñòâàìè. Äëÿ ïðî-
èçâîëüíûõ ìåð ñõîäñòâà (íåìåòðè÷åñêèõ) èòåðàòèâíûì óëó÷øåíèåì ñëó÷àéíî
âûáðàííûõ êàíäèäàòîâ [124] ýìïèðè÷åñêè ïîëó÷åíà ñëîæíîñòü êîíñòðóèðîâà-
íèÿ, ïðèáëèçèòåëüíî ðàâíàÿ O N( ).114 äëÿ áàç ðàçëè÷íîé ðàçìåðíîñòè.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 183
×òîáû óìåíüøèòü âðåìÿ ïîèñêà ïðè ñîõðàíåíèè âûñîêîé âåðîÿòíîñòè íà-
õîæäåíèÿ òî÷íîãî NN, â [125] óäàëÿþò èç ãðàôà KNN ðåáðà, áåç êîòîðûõ àëãî-
ðèòì æàäíîãî ïîèñêà ìîæåò äîñòè÷ü KNN óçëà ïî ñóùåñòâóþùèì ðåáðàì.
 [122] àïïðîêñèìèðóþò ìèíèìàëüíûé ãðàô, êîòîðûé ïîçâîëÿåò æàäíî íàõîäèòü
NN äëÿ îáúåêòîâ-çàïðîñîâ èç áàçû. Ñðåäíåå ÷èñëî ðåáåð ó òàêèõ ãðàôîâ-àïïðîê-
ñèìàöèé íåâåëèêî äëÿ äàííûõ ñ íåâûñîêîé ðàçìåðíîñòüþ.
Äëÿ ïðåîäîëåíèÿ ïðîáëåìû âîçìîæíîé ïîòåðè ñâÿçíîñòè ãðàôà KNN èñ-
ïîëüçóþò óâåëè÷åíèå K è äâóíàïðàâëåííûå ðåáðà ([125, 126] è ïîäðàçä. 3.3.3).
Äðóãîé íåäîñòàòîê — îòñóòñòâèå â îáùåì ñëó÷àå ñâîéñòâ, ïîçâîëÿþùèõ íàõî-
äèòü NN çà poly log N øàãîâ íà îñíîâå ëîêàëüíîé èíôîðìàöèè (æàäíîãî ïîèñêà),
ìîæíî ïðåîäîëåòü ñ ïîìîùüþ ãðàôîâ, îïèñàííûõ â ïîäðàçä. 3.3.3.
3.3.3. Ãðàôû òåñíîãî ìèðà. Â ãðàôàõ ñî ñòðóêòóðîé «òåñíîãî ìèðà» (small
world graph, SWG) ìèíèìàëüíîå ÷èñëî ðåáåð â ïóòè ìåæäó óçëàìè ìåäëåííî (ëî-
ãàðèôìè÷åñêè) ðàñòåò îò êîëè÷åñòâà óçëîâ N [127, 128]. Îòìåòèì, ÷òî äëÿ ëþáîãî
ãðàôà ñ ïîñòîÿííîé ñòåïåíüþ óçëîâ íèæíÿÿ ãðàíèöà äèàìåòðà (âåëè÷èíû ñàìîãî
äëèííîãî êðàò÷àéøåãî ïóòè ìåæäó óçëàìè) ñîñòàâëÿåò � (log )N [129, 130]. Ãðàôû
SWG èìåþò ñâîéñòâî íàâèãàöèè (navigability, NSWG), åñëè æàäíûé àëãîðèòì ïî-
èñêà ïåðåõîäèò èç ëþáîãî èñõîäíîãî â ëþáîé öåëåâîé óçåë çà ñðåäíåå ÷èñëî øàãîâ
(âðåìÿ) O N(poly log ). Íå âñå SWG èìåþò ñâîéñòâî íàâèãàöèè: æàäíûé àëãîðèòì
ïîèñêà íå íàõîäèò êîðîòêîãî ïóòè, õîòÿ îí ñóùåñòâóåò [128, 131]. Äëÿ ïðåâðàùå-
íèÿ íåêîòîðûõ òèïîâ ãðàôîâ â NSWG â [128] ïðåäëîæåíî äîïîëíÿòü èõ äëèííûìè
(long-range) îäíîíàïðàâëåííûìè ðåáðàìè èç îïðåäåëåííîãî ðàñïðåäåëåíèÿ. Îòìå-
òèì, ÷òî ïðîèçâîëüíûé ãðàô íåëüçÿ òàêèì îáðàçîì ïðåâðàòèòü â NSWG: íèæíÿÿ
ãðàíèöà êîëè÷åñòâà øàãîâ äëÿ äîïîëíåííîãî ãðàôà ñóáïîëèíîìèàëüíàÿ
� ( )log2 N [132]. Âåðõíÿÿ ãðàíèöà ñðåäíåãî ÷èñëà øàãîâ
~
( )/O N 1 3 [133] óëó÷øå-
íà äî 2 1log ( )N o� [131].
 [130] ïîêàçàíî, ÷òî ñâîéñòâî NSWG ïîÿâëÿåòñÿ â øèðîêîì êëàññå ñåòåé,
êîíñòðóèðóåìûõ íà îñíîâå åñòåñòâåííûõ è äîâîëüíî îáùèõ ïðèíöèïîâ. Îòìå-
òèì, ÷òî â ãðàôå KNN íåò ìåõàíèçìà ôîðìèðîâàíèÿ «äëèííûõ ðåáåð», ñîåäèíÿ-
þùèõ ðàçëè÷íûå ÷àñòè ãðàôà.
Äëÿ äàííûõ ñ èçâåñòíîé Cd â [112] ïðåäëîæåí àëãîðèòì ïîñòðîåíèÿ visibility
graph — âàðèàíòà NSWG, îáåñïå÷èâàþùåãî æàäíûé òî÷íûé ïîèñê NN çà íå áîëåå
÷åì log N øàãîâ. Òàê êàê ñòåïåíü óçëîâ ãðàôà äîñòèãàåò O D N( 4 log ), âðåìÿ ïîèñ-
êà O D N( log4 2 ), ñëîæíîñòü ïîñòðîåíèÿ poly ( ) log 2D N N . Îäíàêî àëãîðèòì íå
èññëåäîâàí íà ïðàêòèêå.
Ïðàêòè÷åñêèå àëãîðèòìû [120, 121] êîíñòðóèðóþò NSWG èíêðåìåíòíî, âû-
ïîëíÿÿ çàïðîñ KNN ñî âñòàâëÿåìûì îáúåêòîì â êà÷åñòâå îáúåêòà-çàïðîñà è ñâÿ-
çûâàÿ åãî ñ íàéäåííûìè ñîñåäÿìè äâóíàïðàâëåííûìè ðåáðàìè. Âñòàâëåííûå
â íà÷àëå êîíñòðóèðîâàíèÿ ðåáðà óçëîâ âïîñëåäñòâèè ñòàíîâÿòñÿ «äëèííûìè ðåá-
ðàìè». Ïîèñê âûïîëíÿþò æàäíûìè ïðîöåäóðàìè (ïîäðàçä. 3.4.2) ñ íåñêîëüêèìè
ðåñòàðòàìè èç íåïîñåùåííûõ óçëîâ. Ýìïèðè÷åñêè ïðîöåäóðû ïîèñêà è âñòàâêè
èìåþò ïîëèëîãàðèôìè÷åñêóþ ñëîæíîñòü.  [134] îñòàíîâ ïîèñêà âûïîëíÿþò
ïðè íåóëó÷øåíèè ðàññòîÿíèÿ äî çàïðîñà â òå÷åíèå íåñêîëüêèõ èòåðàöèé ïîèñêà,
èñïîëüçóþò òàêæå îáùóþ ïðèîðèòåòíóþ î÷åðåäü èçìåíÿåìîé äëèíû.
Äëÿ ïîâûøåíèÿ ñêîðîñòè ïîèñêà àëãîðèòìà èç [121] (îñîáåííî â áîëüøèõ
áàçàõ ïðè íèçêîé ðàçìåðíîñòè äàííûõ [135, 110]) èåðàðõè÷åñêèé àëãîðèòì
HNSW [136] èíêðåìåíòíî ñòðîèò èåðàðõè÷åñêóþ ñòðóêòóðó ãðàôîâ ñîñåäñòâà
ðàçëè÷íûõ óðîâíåé äëÿ âëîæåííûõ ïîäìíîæåñòâ îáúåêòîâ áàçû (íà âåðõíåì
óðîâíå ìàëîå ÷èñëî îáúåêòîâ, íà íèæíåì — âñå îáúåêòû). Ìàêñèìàëüíûé óðî-
âåíü îáúåêòà âûáèðàåòñÿ ñëó÷àéíî ñ ýêñïîíåíöèàëüíî óáûâàþùåé âåðîÿòíîñòüþ.
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
Ïîèñê ñòàðòóåò ñ âåðõíåãî óðîâíÿ, æàäíî íàõîäèò óçåë ëîêàëüíîãî ìèíèìóìà è
ïðîäîëæàåòñÿ ñ ýòîãî óçëà (èëè ñ íåñêîëüêèõ áëèæàéøèõ ê çàïðîñó) íà íèæíåì
óðîâíå. Íà ñàìîì íèæíåì óðîâíå èñïîëüçóþò áîëåå äëèííóþ ïðèîðèòåòíóþ î÷å-
ðåäü, ÷åì íà îñòàëüíûõ, à íàéäåííûå íà íåì îáúåêòû ÿâëÿþòñÿ îòâåòîì íà çà-
ïðîñ. Äëÿ êîíñòðóèðîâàíèÿ HNSW âûïîëíÿåòñÿ ïîñëåäîâàòåëüíîñòü ïðîöåäóð
âñòàâêè îáúåêòîâ. Íà êàæäîì óðîâíå, íà÷èíàÿ ñ ìàêñèìàëüíîãî óðîâíÿ îáúåêòà è
íèæå, âñòàâëÿåìûé îáúåêò ñîåäèíÿþò ñ K îáúåêòàìè, êîòîðûå íàõîäÿò ìîäèôè-
öèðîâàííîé ïðîöåäóðîé ïîèñêà.
3.4. Èíäåêñíûå ñòðóêòóðû íà îñíîâå ñîõðàíÿþùåãî ñõîäñòâî õýøèðîâà-
íèÿ. Â ëîêàëüíî-÷óâñòâèòåëüíîì õýøèðîâàíèè (locality-sensitive hashing, LSH)
â îòëè÷èå îò îáû÷íîãî LSH-ôóíêöèè ãåíåðèðóþò õýø-çíà÷åíèÿ òàê, ÷òî âåðîÿò-
íîñòü èõ ñîâïàäåíèÿ ó ñõîäíûõ îáúåêòîâ âûøå, ÷åì ó íåñõîäíûõ ([139, 16, 17],
ñì. îáçîð â [11]). Îáúåêòû ñ îäèíàêîâûì õýøåì îáðàçóþò êîðçèíó. Ïðè ïîñòóï-
ëåíèè îáúåêòà-çàïðîñà ãåíåðèðóþò åãî LSH-çíà÷åíèå, èçâëåêàþò èç ñîîòâåòñòâó-
þùåé êîðçèíû îáúåêòû áàçû è èñïîëüçóþò èõ â êà÷åñòâå êàíäèäàòîâ äëÿ ëèíåé-
íîãî ïîèñêà ïî èñõîäíîìó ðàññòîÿíèþ. Õýø-çíà÷åíèÿ ñõîäíûõ îáúåêòîâ, ñãåíå-
ðèðîâàííûå îäíîé LSH-ôóíêöèåé, ìîãóò îêàçàòüñÿ ðàçëè÷íûìè, ïîýòîìó äëÿ
ïîâûøåíèÿ âåðîÿòíîñòè íàõîæäåíèÿ áëèæàéøèõ ê çàïðîñó îáúåêòîâ-êàíäèäàòîâ
ïðè ïîèñêå îáúåäèíÿþò ñïèñêè êàíäèäàòîâ èç êîðçèí íåñêîëüêèõ íåçàâèñèìûõ
LSH-ôóíêöèé (àíàëîãè÷íî ëåñàì äåðåâüåâ, ñì. ïîäðàçä. 2.2.4).
Ïðè íàäëåæàùåì âûáîðå ïàðàìåòðîâ ÈÑ LSH ïîçâîëÿþò ãàðàíòèðîâàòü äëÿ
õóäøåãî ñëó÷àÿ ñóáëèíåéíîå âðåìÿ âûïîëíåíèÿ íåêîòîðûõ òèïîâ çàïðîñîâ ïðè-
áëèæåííîãî ïîèñêà ïî ñõîäñòâó (ñ ðàññ÷èòûâàåìîé âåðîÿòíîñòüþ). Ñåìåéñòâà
LSH-ôóíêöèé ñ èçâåñòíûìè õàðàêòåðèñòèêàìè, ïîçâîëÿþùèìè ðàññ÷èòàòü ïàðà-
ìåòðû ÈÑ, ðàçðàáîòàíû äëÿ íåêîòîðûõ ìåð ðàññòîÿíèÿ/cõîäñòâà âåêòîðíûõ ïðåä-
ñòàâëåíèé; õàðàêòåðèñòèêè íå çàâèñÿò îò êîíêðåòíîãî íàáîðà îáúåêòîâ áàçû.
Äëÿ íåâåêòîðíûõ ïðåäñòàâëåíèé ÈÑ LSH ìîæíî èñïîëüçîâàòü äëÿ ïðèáëè-
æåííîãî ïîèñêà ñ íåêîòîðûìè ãàðàíòèÿìè, åñëè èìåþòñÿ âåêòîðíûå ïðåäñòàâëå-
íèÿ, ðàññòîÿíèÿ êîòîðûõ àïïðîêñèìèðóþò èñõîäíûå ñ èçâåñòíûì èñêàæåíèåì,
è äëÿ ýòèõ âåêòîðîâ ñóùåñòâóåò LSH-ñåìåéñòâî. Íàïðèìåð, äëÿ ðàññòîÿíèÿ Ëå-
âåíøòåéíà ìåæäó ñòðîêàìè èçâåñòíû âëîæåíèÿ â âåêòîðû ñ ðàññòîÿíèåì L1
(ñì. ññûëêè â [10]). Èñïîëüçîâàíèå LSH-ñòðóêòóð äëÿ ïðèáëèæåííîãî ïîèñêà ïî
ðàññòîÿíèþ Ëåâåíøòåéòíà ðàññìîòðåíî â [137, 138].
Àíàëîãè LSH-ôóíêöèé äëÿ îáùèõ ìåòðè÷åñêèõ è íåìåòðè÷åñêèõ ðàññòîÿíèé
èñïîëüçóþò ðàññòîÿíèÿ äî ÎÎ. Îäíàêî ïîèñê íå èìååò ñòðîãèõ ãàðàíòèé LSH,
òàê êàê äëÿ ýòèõ àíàëîãîâ íåèçâåñòíû êîëè÷åñòâåííûå õàðàêòåðèñòèêè, ïîçâîëÿ-
þùèå ðàññ÷èòàòü ÈÑ ââèäó òîãî, ÷òî íåèçâåñòíà ñòðóêòóðà ïðîñòðàíñòâà, à òàêæå
âñëåäñòâèå çàâèñèìîñòè îò âûáîðà ÎÎ. Êðîìå òîãî, LSH-ôóíêöèè ñóùåñòâóþò
òîëüêî äëÿ ìåòðè÷åñêèõ ðàññòîÿíèé [139].
 ðàáîòå [140] â êà÷åñòâå LSH-çíà÷åíèé èñïîëüçóþò ñëó÷àéíî âûáðàííûå
êîìïîíåíòû áèíàðíûõ âåêòîðîâ [105] (ñì. ïîäðàçä. 3.1.3). Â õýøèðîâàíèè DBH
[141] ïðèìåíÿþò FASTMAP äëÿ ïîëó÷åíèÿ (âåêòîðà) âåùåñòâåííûõ èíäåêñíûõ
çíà÷åíèé îáúåêòà. Îòäåëüíûå çíà÷åíèÿ áèíàðèçóþò äâóìÿ ïîðîãàìè (çíà÷åíèå
ìåæäó ïîðîãàìè äàåò 0, èíà÷å 1).  ýêñïåðèìåíòàõ íà áàçàõ ñ íåìåòðè÷åñêèìè
ìåðàìè ðàññòîÿíèÿ ïîëó÷åíî ïðåèìóùåñòâî íàä VPT â ñêîðîñòè ïðè òîé æå òî÷-
íîñòè.  [142] äëÿ îïòèìèçàöèè òî÷íîñòè è âðåìåíè ïîèñêà DBH ïîäñòðàèâàþò
ê áàçå ïóòåì âûáîðà ÎÎ, èõ ïàð, à òàêæå êîëè÷åñòâà õýø-ôóíêöèé.
Àëãîðèòì RBBF [143] èñïîëüçóåò ïðåäñòàâëåíèå îáúåêòà áèòàìè, êàæäûé èõ
êîòîðûõ êîäèðóåò ïîëîæåíèå îáúåêòà îòíîñèòåëüíî îáîáùåííîé ãèïåðïëîñêîñ-
òè (ñì. ïîäðàçä 1.3).
Êîðçèíû DFLSH [144] âêëþ÷àþò îáúåêòû áàçû èç ñâîèõ îáëàñòåé Äèðèõëå
ñî ñëó÷àéíî âûáðàííûìè ÎÎ.  ðàáîòå [145] ÎÎ è îáëàñòè ïîëó÷àþò âàðèàíòà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 185
ìè àëãîðèòìîâ êëàñòåðèçàöèè íà îñíîâå ðàññòîÿíèé K-medoids. Äëÿ óñêîðåíèÿ
ïîèñêà ïðèìåíÿåòñÿ ïàðàëëåëèçàöèÿ. Ïîëíîòà ïîèñêà kNN äîñòèãàåòñÿ íà óðîâíå
DFLSH, îäíàêî âðåìÿ çàïðîñà íåñêîëüêî ìåíüøå âñëåäñòâèå ëó÷øåé
ñáàëàíñèðîâàííîñòè êîðçèí.
 ðàáîòå [146] â êà÷åñòâå îáëàñòåé LSH èñïîëüçóþò îáëàñòè M-index [67] — «âèð-
òóàëüíûå êîðçèíû», ðàçìåð êîòîðûõ ìîæåò èçìåíÿòüñÿ â õîäå âûïîëíåíèÿ çàïðîñà.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåèìóùåñòâî ðàññìîòðåííûõ â îáçîðå ÈÑ çàêëþ÷àåòñÿ â òîì, ÷òî ÿâíî íå
èñïîëüçóþòñÿ ïðåäñòàâëåíèÿ îáúåêòîâ êàê ïðè êîíñòðóèðîâàíèè èíäåêñà, òàê
è ïðè âûïîëíåíèè çàïðîñîâ ïîèñêà ïî ñõîäñòâó. Ýòî ïîçâîëÿåò ïðèìåíÿòü òà-
êèå ñòðóêòóðû äëÿ ïîèñêà ïî ñõîäñòâó îáúåêòîâ ñ ðàçëè÷íûìè òèïàìè ïðåä-
ñòàâëåíèé. Ìåðû ðàññòîÿíèÿ/ñõîäñòâà, ïî êîòîðûì âûïîëíÿåòñÿ ïîèñê, òàêæå
äîñòàòî÷íî ðàçíîîáðàçíû.
Èíäåêñíûå ñòðóêòóðû, ïðåäñòàâëåííûå â ðàçä. 2, ðàáîòàþò ñ ìåðàìè ðàññòîÿ-
íèÿ, êîòîðûå óäîâëåòâîðÿþò ìåòðè÷åñêèì àêñèîìàì. Ïðè êîíñòðóèðîâàíèè èñïîëü-
çóåòñÿ èíôîðìàöèÿ î ðàññòîÿíèè îáúåêòîâ áàçû äî íåêîòîðûõ îïîðíûõ îáúåêòîâ.
Ïðè âûïîëíåíèè ïîèñêîâîãî çàïðîñà ýòà èíôîðìàöèÿ â ñî÷åòàíèè ñ âàðèàíòàìè íå-
ðàâåíñòâà òðåóãîëüíèêà ïðèìåíÿåòñÿ äëÿ áûñòðîãî èñêëþ÷åíèÿ èç îáðàáîòêè îáúåê-
òîâ è ìíîæåñòâ îáúåêòîâ áàçû, êîòîðûå íå ìîãóò ÿâëÿòüñÿ îòâåòîì íà ïîèñêîâûé çà-
ïðîñ (ìåòîä âåòâåé è ãðàíèö, ñì. ïîäðàçä. 1.2), ÷òî äàåò âîçìîæíîñòü óñêîðèòü ïî-
èñê ïî ñðàâíåíèþ ñ ëèíåéíûì ïðè ñîõðàíåíèè òî÷íîñòè ðåçóëüòàòîâ. Íåêîòîðûå
ìåòðè÷åñêèå ðàññòîÿíèÿ èìåþò äîïîëíèòåëüíûå ñâîéñòâà, ïîçâîëÿþùèå èñêëþ÷àòü
èç îáðàáîòêè áîëüøåå êîëè÷åñòâî îáúåêòîâ (ñì. ïîäðàçä. 2.7).
Ïðåäñòàâëåííûå â ðàçä. 2 ÈÑ èìåþò ñëåäóþùèå íåäîñòàòêè. Ñêîðîñòü ïîèñ-
êà ñóùåñòâåííî çàâèñèò îò âûáîðà îïîðíûõ îáúåêòîâ, êîòîðûé îñóùåñòâëÿåòñÿ
ñóáîïòèìàëüíûìè ýâðèñòè÷åñêèìè àëãîðèòìàìè (ñì. ïîäðàçä. 2.6). Êàê è äëÿ
âñåõ ÈÑ òî÷íîãî ïîèñêà ïî ñõîäñòâó, âðåìÿ âûïîëíåíèÿ çàïðîñà ýêñïîíåíöèàëü-
íî çàâèñèò îò âíóòðåííåé ðàçìåðíîñòè äàííûõ: ñ åå ðîñòîì ïîèñê âûðîæäàåòñÿ
â ëèíåéíûé. Óñêîðåíèå ïîèñêà âîçìîæíî òîëüêî çà ñ÷åò ïîòåðè ãàðàíòèé òî÷íîñ-
òè — ïóòåì îáðàáîòêè îáúåêòîâ è èõ ìíîæåñòâ, áëèæàéøèõ ê îáúåêòó-çàïðîñó,
à òàêæå èñêëþ÷åíèÿ íå òîëüêî òåõ æå îáúåêòîâ, ÷òî ïðè òî÷íîì ïîèñêå, íî è
äðóãèõ, êîòîðûå ìîãóò ÿâëÿòüñÿ îòâåòîì íà çàïðîñ, íî ñ ìåíüøåé âåðîÿòíîñòüþ.
Èíäåêñíûå ñòðóêòóðû, ðàññìîòðåííûå â ðàçä. 3, ïðåäíàçíà÷åíû äëÿ ïîèñêà
ïî íåìåòðè÷åñêèì ìåðàì ðàññòîÿíèÿ. Òàê êàê íå ñóùåñòâóåò óíèâåðñàëüíûõ,
ïðèìåíèìûõ êî âñåì íåìåòðè÷åñêèì ðàññòîÿíèÿì óñëîâèé èñêëþ÷åíèÿ íåðåëå-
âàíòíûõ îáúåêòîâ ïðè âûïîëíåíèè çàïðîñà, ÈÑ äëÿ òî÷íîãî ïîèñêà ìåòîäîì âåò-
âåé è ãðàíèö òðåáóþò ó÷åòà ñïåöèôè÷åñêèõ ñâîéñòâ êîíêðåòíûõ íåìåòðèê èëè
èõ êëàññîâ, êîòîðûå ïîçâîëÿþò ðàçðàáîòàòü óñëîâèÿ òî÷íîãî èñêëþ÷åíèÿ, ÷òî
âîçìîæíî äàëåêî íå âñåãäà (ñì. ïîäðàçä. 3.1.1 è 3.1.2).
Äëÿ ïðèáëèæåííîãî ïîèñêà èñïîëüçóþò ïðåîáðàçîâàíèå íåìåòðè÷åñêèõ ðàñ-
ñòîÿíèé ìåæäó îáúåêòàìè ìíîæåñòâà â ìåòðè÷åñêèå (ñì. ïîäðàçä. 3.1.1), à òàêæå
ôîðìèðîâàíèå âåêòîðîâ èëè ìíîæåñòâ ïðèçíàêîâ îáúåêòîâ (ñì. ïîäðàçä. 3.1.2
è 3.1.3), ñõîäñòâî êîòîðûõ îòðàæàåò èñõîäíîå ñõîäñòâî îáúåêòîâ (íî áåç êîëè-
÷åñòâåííûõ ãàðàíòèé èñêàæåíèÿ ñõîäñòâà). Äàëåå èñïîëüçóþò ÈÑ äëÿ áûñòðîãî
ïîèñêà ïî ìåòðè÷åñêèì ðàññòîÿíèÿì, à òàêæå äëÿ âåêòîðîâ è ìíîæåñòâ. Îäíàêî
òî÷íûé ïîèñê â ýòèõ ÈÑ â îáùåì ñëó÷àå íå ãàðàíòèðóåò ïîëó÷åíèÿ ðåçóëüòàòîâ
òî÷íîãî ïîèñêà ïî èñõîäíûì ðàññòîÿíèÿì.
Ïðèâåäåííûå â ïîäðàçä. 3.2, 3.3 ÈÑ âìåñòî èñêëþ÷åíèÿ îáúåêòîâ è îáëàñòåé
ìåòîäîì âåòâåé è ãðàíèö èñïîëüçóþò ïîñëåäîâàòåëüíîñòü ïåðåõîäîâ ê îáúåêòàì
áàçû è èõ ìíîæåñòâàì, ñõîäíûì ñ îáúåêòîì-çàïðîñîì è ñ òåêóùèìè êàíäèäàòà-
ìè. Îãðàíè÷åíèå êîëè÷åñòâà ðàññìàòðèâàåìûõ íà êàæäîì øàãå îáúåêòîâ-êàíäè-
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
äàòîâ ïîçâîëÿåò óñêîðèòü âûïîëíåíèå çàïðîñà. Â ÈÑ, ðàññìîòðåííûõ â ïîä-
ðàçä. 3.4, êàíäèäàòàìè ÿâëÿþòñÿ îáúåêòû áàçû, èìåþùèå òî æå çíà÷åíèå õýøà,
÷òî è îáúåêò-çàïðîñ, ïðè÷åì õýø-çíà÷åíèÿ ãåíåðèðóþòñÿ òàê, ÷òî âåëèêà âåðîÿò-
íîñòü ñîâïàäåíèÿ õýøåé ñõîäíûõ îáúåêòîâ. Òî÷íîñòü ðåçóëüòàòîâ ïðè ñóáëèíåé-
íîì âðåìåíè âûïîëíåíèÿ çàïðîñà â áîëüøèíñòâå ìåòîäîâ íå ãàðàíòèðóåòñÿ, õîòÿ
ýìïèðè÷åñêè ïîëó÷àþò õîðîøèå ðåçóëüòàòû.
Óíèâåðñàëüíûå ÈÑ, ðàçðàáîòàííûå äëÿ ïîèñêà ïî îáùèì íåìåòðè÷åñêèì
ðàññòîÿíèÿì/ñõîäñòâàì, ìîæíî èñïîëüçîâàòü äëÿ ïîèñêà ïî îáùèì ìåòðè÷åñêèì
ðàññòîÿíèÿì, à òàêæå ïî ñïåöèàëüíûì ðàññòîÿíèÿì (âêëþ÷àÿ ðàçëè÷íûå ðàññòîÿ-
íèÿ/ñõîäñòâà ìåæäó âåêòîðàìè).
Îòìåòèì, ÷òî äëÿ íåêîòîðûõ òèïîâ çàïðîñîâ ïîèñêà ïî ñõîäñòâó îáúåêòîâ,
ïðåäñòàâëåííûõ âåêòîðàìè, ðàçðàáîòàíû ÈÑ, îáåñïå÷èâàþùèå ïðèáëèæåííûé ïî-
èñê ñ ãàðàíòèÿìè ñóáëèíåéíîãî âðåìåíè, à òàêæå êà÷åñòâà ðåçóëüòàòîâ äëÿ õóäøåãî
ñëó÷àÿ, òàêèå êàê LSH [16, 17] è LSF [147] (ñì. òàêæå ïîäðàçä. 3.4). Ýêñïåðèìåí-
òàëüíîå ñðàâíåíèå [136, 148] ðåàëèçàöèé ðÿäà èç ðàññìîòðåííûõ â íàñòîÿùåì îáçîðå
ÈÑ ïîêàçûâàåò, ÷òî â íàñòîÿùåå âðåìÿ íàèëó÷øèå ðåçóëüòàòû ïîèñêà äåìîíñòðèðó-
åò èåðàðõè÷åñêàÿ ñòðóêòóðà íà îñíîâå ãðàôîâ òåñíîãî ìèðà ñî ñâîéñòâîì íàâèãàöèè
HNSW (ñì. ïîäðàçä. 3.3.3). Äëÿ HNSW íà áîëüøèõ áàçàõ ýìïèðè÷åñêè ïîëó÷åíà ëî-
ãàðèôìè÷åñêàÿ ñëîæíîñòü ïîèñêà. Ïîêàçàíî ïðåèìóùåñòâî HNSW íàä ìíîãèìè
ëó÷øèìè ÈÑ äëÿ ïîèñêà ïî íåâåêòîðíûì äàííûì: VP-tree, NAPP, NSW, ãðàô KNN
[124]. Ïîäáîð ïàðàìåòðîâ ïîçâîëÿåò äëÿ íåêîòîðûõ àëãîðèòìîâ, âêëþ÷àÿ HNSW, íà
íåêîòîðûõ áàçàõ ïîëó÷àòü òî÷íûå ðåçóëüòàòû ïîèñêà (çà ñ÷åò óâåëè÷åíèÿ âðåìåíè
âûïîëíåíèÿ çàïðîñà ïî ñðàâíåíèþ ñ ïðèáëèæåííûì ïîèñêîì). Îòìåòèì, ÷òî äëÿ
ïîèñêà ïî âåêòîðíûì äàííûì HNSW äàåò ðåçóëüòàòû âûøå, ÷åì ëó÷øèå ñòðóêòóðû,
ñïåöèàëèçèðîâàííûå äëÿ âåêòîðíûõ ïðåäñòàâëåíèé [136].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. 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.
2. Manning C., Raghavan P., Sch��utze H. Introduction to information retrieval. New York: Cambridge Uni-
versity Press, 2008. 506 p.
3. Duda R.O., Hart P.E., Stork D.G. Pattern classification. 2nd Edition. New York: John Wiley & Sons,
2001. 680 p.
4. Lopez De Mantaras R., Mcsherry D., Bridge D., Leake D., Smyth B., Craw S., Faltings B., Maher M.L.,
Cox M.T., Forbus K., Keane M., Aamodt A., Watson I.. Retrieval, reuse, revision and retention in
case-based reasoning. Knowledge Engineering Review. 2005. Vol. 20, N 3. P. 215–240.
5. Voskoglou M.G., Salem A.-B.M. Analogy-based and case-based reasoning: Two sides of the same coin.
IJAFSAI. 2014. Vol. 4. P. 5–51.
6. Wharton C.M., Holyoak K.J., Downing P.E., Lange T.E., Wickens T.D., Melz E.R. Below the surface:
Analogical similarity and retrieval competition reminding. Cognitive Psychology. 1994. Vol. 26.
P. 64–101.
7. Gentner D., Smith L. Analogical reasoning. In: Encyclopedia of human behavior. V.S. Ramachandran
(Ed.) (2nd ed.). Oxford, UK: Elsevier, 2012. Vol. 1. P. 130–136.
8. 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.
9. Forbus K., Ferguson R., Lovett A., Gentner D. Extending SME to handle large-scale cognitive modeling.
Cognitive Science. DOI: 10.1111/cogs.12377.
10. Rachkovskij D.A. Real-valued embeddings and sketches for fast distance and similarity estimation. Cy-
bernetics and Systems Analysis. 2016. Vol. 52, N. 6. P. 967–988.
11. Rachkovskij D.A. Binary vectors for fast distance and similarity estimation. Cybernetics and Systems
Analysis. 2017. Vol. 53, N 1. P. 138–156.
12. Chavez E., Navarro G., Baeza-Yates R., Marroquin J.L. Searching in metric spaces. ACM Computing Sur-
veys. 2001. Vol. 33, N 3. P. 273–321.
13. Hjaltason G.R., Samet H. Index-driven similarity search in metric spaces. ACM Transactions on Database
Systems. 2003. Vol. 28, N 4. P. 517–580.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 187
14. Samet H. Foundations of multidimensional and metric data structures. San Francisco: Morgan Kaufmann,
2006. 1024 p.
15. Zezula P., Amato G., Dohnal V., Batko M. Similarity search: The metric space approach. New York:
Springer, 2006. 220 p.
16. 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.
17. Andoni A., Indyk P. Nearest neighbors in high-dimensional spaces. In: Handbook of discrete and compu-
tational geometry. 3rd edition. 2017 (to appear). Chap. 43.
18. Fukunaga K., Narendra P.M. A branch and bound algorithm for computing k-nearest neighbors. IEEE
Trans. Comput. 1975. Vol. C-24, N 7. P. 750–753.
19. Lokoc J., Skopal T. On applications of parameterized hyperplane partitioning. Proc. SISAP’10. 2010.
P. 131–132.
20. Cayton L. Efficient Bregman range search. Proc. NIPS’09. 2009. P. 243-251.
21. Connor R., Vadicamo L., Cardillo F.A., Rabitti F. Supermetric search with the four-point property. Proc.
SISAP’16. 2016. P. 51–64.
22. Hjaltason G.R., Samet H. Properties of embedding methods for similarity searching in metric spaces.
IEEE Trans. PAMI. 2003. Vol. 25, N 5. P. 530–549.
23. Clarkson K. Nearest-neighbor searching and metric space dimensions. In: Nearest-neighbor methods for
learning and vision: Theory and practice. MIT Press, 2006. P. 15–59.
24. Weber R., Schek H.J., Blott S. A quantitative analysis and performance study for similarity-search meth-
ods in high-dimensional spaces. Proc. VLDB’98. 1998. P.194–205.
25. B��ohm Ñ., Berchtold S., Keim D.A. Searching in high-dimensional spaces: Index structures for improving
the performance of multimedia databases. ACM Com. Surv. 2001. Vol. 33, N 3. P. 322–373.
26. Beyer K., Goldstein J., Ramakhrishnan R., Shaft U. When is “nearest neighbor” meaningful? Proc.
ICDT’99. 1999. P. 217–235.
27. Shaft U., Ramakrishnan R. Theory of nearest neighbors indexability. ACM Trans. Database Syst. 2006.
Vol. 31. P. 814–838.
28. Volnyansky I., Pestov V. Curse of dimensionality in pivot based indexes. Proc. SISAP’09. 2009.
P. 39–46.
29. Pestov V. Indexability, concentration, and VC theory. Journal of Discrete Algorithms. 2012. Vol. 13.
P. 2–18.
30. Camastra F. Data dimensionality estimation methods: a survey. Pattern Recogn. 2003. Vol. 6, N 12.
P. 2945–2954.
31. Traina C., Santos Filho R.F., Traina A.J.M, Vieira M.R., Faloutsos C. The Omni-family of all-purpose ac-
cess methods: A simple and effective way to make similarity search more efficient. VLDB Journal. 2007.
Vol. 16, N 4. P. 483–505.
32. Skopal T., Bustos B. On nonmetric similarity search problems in complex domains. ACM Comput. Sur-
veys. 2011. Vol. 43, N 4. P. 34:1–34:50.
33. Mao R., Mirankerb W.L., Mirankerc D.P. Pivot selection: Dimension reduction for distance-based index-
ing. J. Discrete Algorithms. 2012. Vol. 13. P. 32–46.
34. Patella M., Ciaccia P. Approximate similarity search: a multi-faceted problem. J. Discrete Algorithms.
2009. Vol. 7, N 1. P. 36–48.
35. Powers D.M.W. Evaluation: from precision, recall and F-measure to ROC, informedness, markedness and
correlation. J. of Machine Learning Tech. 2011. Vol. 2, N 1. P. 37–63.
36. Muja M., Lowe D.G. Scalable nearest neighbor algorithms for high dimensional data. IEEE TPAMI. 2014.
Vol. 36, N 11. P. 2227–2240.
37. Navarro G. Analyzing metric space indexes: What for? Proc. SISAP’09. 2009. P. 3–10.
38. Vidal E. An algorithm for finding nearest neighbors in (approximately) constant average time. Patt.
Recog. Lett. 1986. Vol. 4, N3. P. 145–157.
39. Vidal E. New formulation and improvements of the nearest-neighbour approximating and eliminating
search algorithm (AESA). Patt. Recog. Lett. 1994. Vol. 15, N 1. P. 1–7.
40. Figueroa K., Chavez E., Navarro G., Paredes R. Speeding up spatial approximation search in metric
spaces. ACM Journal of Experimental Algorithmics. 2009. Vol. 14. P. 3.6.1–3.6.21.
41. Mico L., Oncina J., Vidal E. A new version of the nearest-neighbor approximating and eliminating search
(AESA) with linear preprocessing-time and memory requirements. Patt. Recog. Lett. 1994. Vol. 15, N 1.
P. 9–17.
42. Nene S., Nayar S. A simple algorithm for nearest neighbor search in high dimensions. IEEE Trans. PAMI.
1997. Vol. 19, N 9. P. 989–1003.
43. Chavez E., Marroqu�n J., Baeza-Yates R. Spaghettis: an array based algorithm for similarity queries in
metric spaces. Proc. SPIRE’99. 1999. P. 38–46.
44. Munro I., Raman R., Raman V., Rao S.S. Succinct representations of permutations and functions. Theor.
Comput. Sci. 2012. Vol. 438. P. 74–88.
188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
45. Chavez E., Ruiz U., Tellez E. CDA: Succinct spaghetti. Proc. SISAP’15. 2015. P. 54–64.
46. Tokoro K., Yamaguchi K., Masuda S. Improvements of TLAESA nearest neighbour search algorithm and
extension to approximation search. Proc. ACSC’06. 2006. P. 77–83.
47. Ruiz G., Santoyo F., Chavez E., Figueroa K., Tellez E. Extreme pivots for faster metric indexes. Proc.
SISAP’13. 2013. P. 115–126.
48. Uhlmann J.K. Satisfying general proximity/similarity queries with metric trees. Information Processing
Letters. 1991. Vol. 40, N4. P. 175–179.
49. Yianilos P.N. Data structures and algorithms for nearest neighbor search in general metric spaces. Proc.
SODA’93. 1993. P. 311–321.
50. Chiueh T. Content-based image indexing. Proc. VLDB’94. 1994. P. 582–593.
51. Bozkaya T., Ozsoyoglu M. Indexing large metric spaces for similarity search queries. ACM Trans. Datab.
Syst. 1999. Vol. 24, N 3. P. 361–404.
52. Fu A.W.-C., Chan P.M.-S., Cheung Y.-L., Moon Y.S. Dynamic vp-tree indexing for n-nearest neighbor
search given pair-wise distances. VLDB Journal. 2000. Vol. 9, N 2. P. 154–173.
53. Yianilos P. Excluded middle vantage point forests for nearest neighbor search. In: DIMACS Implementa-
tion Challenge, ALENEX’1999. URL: http://citeseer.ist.psu.edu/.
54. Kalantari I., Mcdonald G. A data structure and an algorithm for the nearest point problem. IEEE Trans.
Softw. Eng. 1983. Vol. 9, N 5. P. 631–634.
55. Dehne F., Noltemeier H. Voronoi trees and clustering problems. Information Systems. 1987. Vol. 12, N 2.
P. 171–175.
56. Noltemeier H., Verbarg K., Zirkelbach C. Monotonous bisector* trees — A tool for efficient partitioning
of complex scenes of geometric objects. LNCS. 1992. Vol. 594. P. 186–203.
57. Ciaccia P., Patella M., Zezula P. Mtree: An efficient access method for similarity search in metric spaces.
Proc. VLDB’97. 1997. P. 426–435.
58. Zezula P., Savino P., Amato G., Rabitti F. Approximate similarity retrieval with M-trees. VLDB Journal.
1998. Vol. 7, N 4. P. 275–293.
59. Skopal T., Pokorny J., Snasel V. PM-tree: PM-tree: pivoting metric tree for similarity search in multime-
dia databases. Proc. ADBIS’04. 2004. P. 99–114.
60. Jin S., Kim O., Feng W. MX-tree: A double hierarchical metric index with overlap reduction. Proc.
ICCSA’13. 2013. P. 574–589.
61. Brin S. Near neighbor search in large metric spaces. Proc. VLDB’95. 1995. P. 574–584.
62. Fredriksson K. Geometric near-neighbor access tree (GNAT) revisited. arXiv:1605.05944. 20 May 2016.
63. Navarro G., Uribe R. Fully dynamic metric access methods based on hyperplane partitioning. Information
Systems. 2011. Vol. 36, N 4. P. 734–747.
64. Connor R. Reference point hyperplane trees. Proc. SYSAP’16. 2016. P. 65–78.
65. O’Hara S., Draper B.A. Are you using the right approximate nearest neighbor algorithm? Proc. WACV’13.
2013. P. 9–14.
66. Comer D. The ubiquitous B-tree. ACM Comput. Surv. 1979. Vol. 11. P. 121–138.
67. Novak D., Batko M. Metric Index: An efficient and scalable solution for precise and approximate similar-
ity search. Information Systems. 2011. Vol. 36, N 4. P. 721–733.
68. Lokoc J., Mosko J., Cech P., Skopal T. On indexing metric spaces using cut-regions. Information Systems.
2014. Vol. 43. P. 1–19.
69. Chen L., Gao Y., Li X., Jensen C.S., Chen G. Efficient metric indexing for similarity search. Proc.
ICDE’15. 2015. P. 591–602.
70. Navarro G. Searching in metric spaces by spatial approximation. VLDB Journal. 2002. Vol. 11, N 1.
P. 28–46.
71. Navarro G., Reyes N. Dynamic spatial approximation trees. Journal of Experimental Algorithmics. 2009.
Vol. 12. Article 1.5. 68 p.
72. Barroso M., Reyes N., Paredes R. Enlarging nodes to improve spatial approximation trees. Proc.
SISAP’10. 2010. P. 41–48.
73. Navarro G., Reyes N. New dynamic metric indices for secondary memory. Information Systems. 2016.
Vol. 59. P. 48–78.
74. Chavez E., Luduena V., Reyes N., Roggero P. Faster proximity searching with the distal SAT. Informa-
tion Systems. 2016. Vol. 59. P. 15–47.
75. Beygelzimer A., Kakade S., Langford J.C. Cover trees for nearest neighbor. Proc. ICML’06. 2006.
P. 97–104.
76. Curtin R.R. Improving dual-tree algorithms: Ph.D. thesis. Georgia Inst. Tech. 2015. 246 p.
77. Chavez E., Navarro G. A compact space decomposition for effective metric indexing. Pattern Recognition
Letters. 2005. Vol. 26, N 9. P. 1363–1376.
78. Roggero P., Reyes N., Figueroa K., Paredes R. List of clustered permutations in secondary memory for
proximity searching. J. of Com. Science Tech. 2015. Vol. 15, N 2. P. 107–113.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 189
79. Ponomarenko A., Avrelin N., Naidan B., Boytsov L. Comparative analysis of data structures for approxi-
mate nearest neighbor search. DATA ANALYTICS 2014. 2014. P. 125–130.
80. Dohnal V., Gennaro C., Savino P., Zezula P. D-index: Distance searching index for metric data sets. Mul-
timedia Tools and Applications. 2003. Vol. 21, N 1. P. 9–33.
81. Cayton L. Accelerating nearest neighbor search on manycore systems. Proc. IPDPS’12. 2012. P. 402–413.
82. Tellez E.S., Ruiz G., Chavez E. Singleton indexes for nearest neighbor search. Information Systems. 2016.
Vol. 60. P. 50–68.
83. Rosenkrantz D.J., Stearns R.E., Lewis P.M. II. An analysis of several heuristics for the traveling salesman
problem. SIAM Journal on Computing. 1977. Vol. 6, N 3. P. 563–581.
84. Gonzalez T.F. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science.
1985. Vol. 38. P. 293–306.
85. Bustos B., Navarro G., Chavez E. Pivot selection techniques for proximity searching in metric spaces.
Pattern Recogn. Lett. 2003. Vol. 24. P. 2357–2366.
86. Brisaboa N.R., Farina A., Pedreira O., Reyes N. Similarity search using sparse pivots for efficient multi-
media information retrieval. Proc. ISM’06. 2006. P. 881–888.
87. Van Leuken R.H., Veltkamp R.C. Selecting vantage objects for similarity indexing. ACM Trans. Multime-
dia Comput. Commun. Appl. 2011. Vol. 7. P. 16:1–16:18.
88. Kim S.-H., Lee D.-Y., Cho H.-G. An eigenvalue-based pivot selection strategy for improving search effi-
ciency in metric spaces. Proc. BigComp’16. 2016. P. 207–214.
89. Berman A., Shapiro L.G. Selecting good keys for triangle-inequality-based pruning algorithms. Proc.
CAIVD’98. 1998. P. 12–19.
90. Venkateswaran J., Kahveci T., Jermaine C.M., Lachwani D. Reference-based indexing for metric spaces
with costly distance measures. VLDB Journal. 2008. Vol. 17, N 5. P. 1231–1251.
91. Mao R., Zhang P., Li X., Xi L., Lu M. Pivot selection for metric-space indexing. Int. J. Mach. Learn.
Cybern. 2016. Vol. 7, N 2. P. 311–323.
92. Celik C. Effective use of space for pivot-based metric indexing structures. Proc. SISAP’08. 2008.
P. 113–120.
93. Hetland M.L., Skopal T., Lokoc J., Beecks C. Ptolemaic access methods: Challenging the reign of the
metric space model. Information Systems. 2013. Vol. 38, N 7. P. 989–1006.
94. Hetland M.L. Ptolemaic indexing. JoCG. 2015. Vol. 6, N 1. P. 165–184.
95. Connor R., Vadicamo L., Cardillo F.A., Rabitti F. Supermetric search with the four-point property. Proc.
SISAP’16. 2016. P. 51–64.
96. Ciaccia P., Patella M. Searching in metric spaces with user-defined and approximate distances. ACM Da-
tabase Systems. 2002. Vol. 27, N 4. P. 398–437.
97. Chen L., Lian X. Efficient similarity search in nonmetric spaces with local constant embedding. IEEE
TKDE. 2008. Vol. 20, N 3. P. 321–336.
98. Skopal T., Lokoc J. NM-tree: Flexible approximate similarity search in metric and non-metric spaces.
Proc. DEXA’08. 2008. P. 312–325.
99. Curtin R.R., Ram P., Gray A.G. Fast exact max-kernel search. Proc. SDM’13. 2013. P. 1–9.
100. Keogh E., Ratanamahatana C. Exact indexing of dynamic time warping. Knowledge and Information Sys-
tems. 2005. Vol. 7, N 3. P. 358–386.
101. Zhang Z., Ooi B.C., Parthasarathy S., Tung A.K.H. Similarity search on bregman divergence: towards
non-metric indexing. Proc. VLDB Endowment. 2009. Vol. 2. P. 13–24.
102. Abdullah A., Moeller J., Venkatasubramanian S. Approximate Bregman near neighbors in sublinear time:
Beyond the triangle inequality. Proc. SCG’12. 2012. P. 31–40.
103. Amato G., Savino P. Approximate similarity search in metric spaces using inverted files. Proc.
InfoScale’08. 2008. P. 28:1–28:10.
104. Chavez E., Figueroa K., Navarro G. Effective proximity retrieval by ordering permutations. IEEE TPAMI.
2008. Vol. 30, N 9. P. 1647–1658.
105. Tellez E.S., Chavez E., Camarena-Ibarrola A. A brief index for proximity searching. Proc. CIARP’09.
2009. P. 529–536.
106. Amato G., Gennaro C., Savino P. Mi-file: using inverted files for scalable approximate similarity search.
Multimed. Tools Appl. 2014. Vol. 71, N 3. P. 1333–1362.
107. Esuli A. Use of permutation prefixes for efficient and scalable approximate similarity search. Information
Processing & Management. 2012. Vol 48, N 5. P. 889–902.
108. Tellez E.S., Chavez E., Navarro G. Succinct nearest neighbor search. Information Systems. 2013. Vol. 38,
N 7. P. 1019–1030.
109. Chavez E., Graff M., Navarro G., Tellez E. Near neighbor searching with K nearest references. Informa-
tion Systems. 2015. Vol. 51. P. 43–61.
110. Naidan B., Boytsov L., Nyberg E. Permutation search methods are efficient, yet faster search is possible.
Proc. VLDB Endowment. 2015. Vol. 8, N. 12. P. 1618–1629.
190 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
111. Goyal N., Lifshits Y., Schutze H. Disorder inequality: A combinatorial approach to nearest neighbor
search. Proc. WSDM’08. 2008. P. 25–32.
112. Lifshits Y., Zhang S. Combinatorial algorithms for nearest neighbors, near-duplicates and small world de-
sign. Proc. SODA’09. 2009. P. 318–326.
113. Tschopp D., Diggavi S.N., Delgosha P., Mohajer S. Randomized algorithms for comparison-based search.
Proc. NIPS’11. 2011. P. 2231–2239.
114. Houle M.E., Sakuma J. Fast approximate similarity search in extremely high-dimensional data sets. Proc.
ICDE’05. 2005. P. 619–630.
115. Houle M.E., Nett M. Rank-based similarity search: Reducing the dimensional dependence. IEEE TPAMI.
2015. Vol. 37, N 1. P. 136–150.
116. Arya S., Mount D.M. Approximate nearest neighbor queries in fixed dimensions. Proc. SODA’93. 1993.
P. 271–280.
117. Sebastian T., Kimia B. Metric-based shape retrieval in large databases. Proc. ICPR’02. 2002. Vol. 3.
P. 291–296.
118. Paredes R., Chavez E. Using the k-nearest neighbor graph for proximity searching in metric spaces. Proc.
SPIRE’05. 2005. P. 127–138.
119. Hajebi K., Abbasi-Yadkori Y., Shahbazi H., Zhang H. Fast approximate nearest-neighbor search with
K-nearest neighbor graph. Proc. IJCAI’11. 2011. P. 1312–1317.
120. Malkov Y., Ponomarenko A., Logvinov A., Krylov V. Scalable distributed algorithm for approximate
nearest neighbor search problem in high dimensional general metric spaces. Proc. SISAP’12. 2012.
P. 132–147.
121. Malkov Y., Ponomarenko A., Logvinov A., Krylov V. Approximate nearest neighbor algorithm based on
navigable small world graphs. Information Systems. 2014. Vol. 45. P.61–68.
122. Harwood B., Drummond T. FANNG: fast approximate nearest neighbour graphs. Proc. CVPR’16. 2016.
P. 5713–5722.
123. Paredes R., Chavez E., Figueroa K., Navarro G. Practical construction of k-nearest neighbor graphs in
metric spaces. Proc. WEA’06. 2006. P. 85–97.
124. Dong W., Charikar M., Li K. Efficient K-nearest neighbor graph construction for generic similarity mea-
sures. Proc. WWW’11. 2011. P. 577–586.
125. Aoyama K., Saito K., Sawada H., Ueda N. Fast approximate similarity search based on degree-reduced
neighborhood graphs. Proc. KDD’11. 2011. P. 1055–1063.
126. Li W., Zhang Y., Sun Y., Wang W., Zhang W., Lin X. Approximate nearest neighbor search on high di-
mensional data — experiments, analyses, and improvement. arXiv:1610.02455. 8 Oct 2016.
127. Watts D.J., Strogatz S.H. Collective dynamics of small-world networks. Nature. 1998. Vol. 393, N 6684.
P. 440–442.
128. Kleinberg J. The small-world phenomenon: an algorithmic perspective. Proc. STOC’00. 2000. P. 163–170.
129. Chung F.R.K. Diameters of graphs: old problems and new results. Congr. Numer. 1987. Vol. 60. P. 295–317.
130. Achlioptas D., Siminelakis P. Navigability is a robust property. Proc. WAW’15. 2015. P. 78–91.
131. Fraigniaud P., Giakkoupis G. On the searchability of small-world networks with arbitrary underlying
structure. Proc. STOC’10. 2010. P. 389–398.
132. Fraigniaud P., Lebhar E., Lotker Z. A lower bound for network navigability. SIAM Journal on Discrete
Mathematics. 2010. Vol. 24, N 1. P. 72–81.
133. Fraigniaud P., Gavoille C., Kosowski A., Lebhar E., Lotker Z. Universal augmentation schemes for net-
work navigability: Overcoming the n-barrier. Proc. SPAA’07. 2007. P. 1–7.
134. Ruiz G., Chavez E., Graff M., Tellez E.S. Finding near neighbors through local search. Proc. SISAP’15.
2015. P. 103–109.
135. Ponomarenko A., Avrelin N., Naidan B., Boytsov L. Comparative analysis of data structures for approxi-
mate nearest neighbor search. Proc. Data Analytics’14. 2014. P. 125–130.
136. Malkov Yu.A., Yashunin D.A. Efficient and robust approximate nearest neighbor search using Hierarchi-
cal Navigable Small World graphs. arXiv:1603.09320. 21 May, 2016.
137. Sokolov A. Vector representations for efficient comparison and search for similar strings. Cybernetics and
Systems Analysis. 2007. Vol. 43, N 4. P. 484–498.
138. Sokolov A. Investigation of accelerated search for close text sequences with the help of vector representa-
tions. Cybernetics and Systems Analysis. 2008. Vol. 44, N 4. P. 493–506.
139. Charikar M. Similarity estimation techniques from rounding algorithms. Proc. STOC’02. 2002. P. 380–388.
140. Tellez E.S., Chavez E. On locality sensitive hashing in metric spaces. Proc. SISAP’10. 2010. P. 67–74.
141. Athitsos V., Potamias M., Papapetrou P., Kollios G. Nearest neighbor retrieval using distance-based hash-
ing. Proc. ICDE’08. 2008. P. 327–336.
142. Jangyodsuk P., Papapetrou P., Athitsos V. Optimizing hashing functions for similarity indexing in arbi-
trary metric and nonmetric spaces. Proc. SDM’15. 2015. P. 828–836.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 191
143. Andrade J.M., Astudillo C.A, Paredes R. Metric space searching based on random bisectors and binary
fingerprints. Proc. SISAP’14. 2014. P. 50–57.
144. Kang B., Jung K. Robust and efficient locality sensitive hashing for nearest neighbor search in large data
sets. Proc. BigLearn’12. 2012. P. 1–8.
145. Silva E.S, Teixeira T.S.F.X, Teodoro G., Valle E. Large-scale distributed locality-sensitive hashing for
general metric data. Proc. SISAP’14. 2014. P. 82–93.
146. Novak D., Kyselak M., Zezula P. On locality-sensitive indexing in generic metric spaces. Proc. SISAP’10.
2010. P. 59–66.
147. 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.
148. ANN benchmark. http://github.com/erikbern/ann-benchmarks. Accessed 12 Apr. 2017.
Íàä³éøëà äî ðåäàêö³¿ 07.07.2016
Ä.À. Ðà÷êîâñüêèé
ÎÑÍÎÂÀͲ ÍÀ ²ÄÑÒÀÍßÕ ²ÍÄÅÊÑͲ ÑÒÐÓÊÒÓÐÈ ÄËß ØÂÈÄÊÎÃÎ
ÏÎØÓÊÓ ÇÀ ÑÕÎƲÑÒÞ
Àíîòàö³ÿ. Ðîçãëÿíóòî êëàñ òàêèõ ³íäåêñíèõ ñòðóêòóð äëÿ øâèäêîãî ïîøóêó
çà ñõîæ³ñòþ, ïðè êîíñòðóþâàíí³ òà çàñòîñóâàíí³ ÿêèõ âèêîðèñòîâóþòü
ò³ëüêè ³íôîðìàö³þ ïðî çíà÷åííÿ àáî ðàíã äåÿêèõ â³äñòàíåé/ñõîæîñòåé ì³æ
îá’ºêòàìè. Îáãîâîðåíî ïîøóê ÿê çà ìåòðè÷íèìè â³äñòàíÿìè (äëÿ ÿêèõ âèêî-
íóºòüñÿ íåð³âí³ñòü òðèêóòíèêà òà ³íø³ ìåòðè÷í³ àêñ³îìè), òàê ³ çà íåìåòðè÷-
íèìè. Íàâåäåíî ñòðóêòóðè, ÿê³ ïîâåðòàþòü îá’ºêòè áàçè, ùî º òî÷íîþ
â³äïîâ³ääþ íà çàïèò, à òàêîæ ñòðóêòóðè äëÿ íàáëèæåíîãî ïîøóêó çà
ñõîæ³ñòþ (âîíè íå ãàðàíòóþòü òî÷íîñò³, àëå çàçâè÷àé ïîâåðòàþòü áëèçüê³ äî
òî÷íèõ ðåçóëüòàòè òà ïðàöþþòü øâèäøå ñòðóêòóð äëÿ òî÷íîãî ïîøóêó).
Âèêëàäåíî çàãàëüí³ ïðèíöèïè êîíñòðóþâàííÿ ³ çàñòîñóâàííÿ äåÿêèõ ³íäåê-
ñíèõ ñòðóêòóð, à òàêîæ ðîçãëÿíóòî ³äå¿, íà ÿêèõ áàçóþòüñÿ êîíêðåòí³ àëãî-
ðèòìè (â³äîì³ òà çàïðîïîíîâàí³ îñòàíí³ì ÷àñîì).
Êëþ÷îâ³ ñëîâà: ïîøóê çà ñõîæ³ñòþ, ïîøóê íàéáëèæ÷èõ ñóñ³ä³â, ³íäåêñí³
ñòðóêòóðè, ³íäåêñóâàííÿ íà îñíîâ³ â³äñòàíåé, ìåòðè÷íà â³äñòàíü, íåìåòðè÷íà
â³äñòàíü, ìåòðè÷íå äåðåâî, ãðàô ñóñ³äñòâà, ìåòîä ã³ëîê ³ ìåæ.
D.A. Rachkovskij
DISTANCE-BASED INDEX STRUCTURES FOR FAST SIMILARITY SEARCH
Abstract. In this survey paper we consider the class of index structures for fast
similarity search that uses for index construction and application only
information about the values or ranks of some distances/similarities between
objects. We discuss the search by metric distances (for which the triangle
inequality and other metric axioms are valid), as well as by non-metric ones.
Considered index structures include those returning the objects of the base that
are exact results to the similarity search query, and index structures for
approximate similarity search, which do not guarantee the accuracy, but usually
return close to accurate results and work faster than the structures for exact
search. Some general principles for construction and usage of index structures as
well as some ideas of specific algorithms, including recently proposed ones, are
discussed.
Keywords: similarity search, nearest neighbor search, index structures, distance-
based indexing, metric distances, non-metric distances, metric trees, proximity
graph, branch and bound.
Ðà÷êîâñêèé Äìèòðèé Àíäðååâè÷,
äîêòîð òåõí. íàóê, âåäóùèé íàó÷íûé ñîòðóäíèê Ìåæäóíàðîäíîãî íàó÷íî-ó÷åáíîãî öåíòðà èíôîð-
ìàöèîííûõ òåõíîëîãèé è ñèñòåì ÍÀÍ Óêðàèíû è ÌÎÍ Óêðàèíû, Êèåâ, e-mail: dar@infrm.kiev.ua.
192 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4
|