Index structures for fast similarity search of real-valued vectors. I / Rachkovskij. (2018)
Ukrainian

web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000805867
  Cybernetics and Systems Analysis      А - 2019  /     Issue (2018, Т. 54, № 1)

Рачковский Д. А.
Индексные структуры для быстрого поиска по сходству вещественных векторов. I

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

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь и некоторые теоретические аспекты.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Приведены главным образом индексные структуры на основании разбиения на области (в том числе иерархические) и графов соседства. Обсуждено также ускорение поиска по сходству с использованием преобразования исходных данных. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Проведено сравнение подходов к ускорению поиска по сходству в индексных структурах рассмотренных типов, а также на основе сохраняющего сходство хэширования.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Приведены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.

 https://doi.org/10.1007/s10559-018-0034-z
 Scopus

Бібліографічний опис:
Рачковский Д. А.  Индексные структуры для быстрого поиска по сходству вещественных векторов. I. Кибернетика и системный анализ. 2018. Т. 54, № 1. С. 168-183. doi: https://doi.org/10.1007/s10559-018-0034-z URL: http://jnas.nbuv.gov.ua/article/UJRN-0000805867

English  Cybernetics and Systems Analysis   /     Issue (2018, 54 (1))

Rachkovskij D.A.
Index structures for fast similarity search of real-valued vectors. I

This survey article considers index structures for fast similarity search for objects represented by real-valued vectors. Structures for both exact and faster but approximate similarity search are considered. Index structures based on partitioning into regions (including hierarchical ones) and on proximity graphs are mainly presented. The acceleration of similarity search using the transformation of initial data is also discussed. The ideas of concrete algorithms including recently proposed ones are outlined. The approaches to the acceleration of similarity search in index structures of the considered types and also on the basis of similarity-preserving hashing are discussed and compared. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: branch and bound method, clustering, index structure, locality-sensitive hashing, near neighbor, nearest neighbor, proximity graph, similarity search, tree and forest, Metadata, Nearest neighbor search, clustering, Index structure, Locality sensitive hashing, near neighbor, Nearest neighbors, Proximity graphs, Similarity search, tree and forest, Branch and bound method

Cite:
Rachkovskij D.A. (2018). Index structures for fast similarity search of real-valued vectors. I. Cybernetics and Systems Analysis, 54 (1), 168-183. doi: https://doi.org/10.1007/s10559-018-0034-z http://jnas.nbuv.gov.ua/article/UJRN-0000805867 [In Russian].

 

Institute of Information Technologies of VNLU

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Ukraine, 03039, Kyiv, Holosiivskyi Ave, 3, room 209