web address of the page http://jnas.nbuv.gov.ua/article/UJRN-0000754495
Cybernetics and Systems Analysis   А - 2019 /  Issue (2017, Т. 53, № 5)
Рачковский Д. А.
Индексные структуры для быстрого поиска по сходству бинарных векторов Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Приведены, главным образом, индексные структуры на основе хэш-таблиц, сохраняющего сходство хэширования, а также древовидных структур, графов соседства и нейросетевой распределенной автоассоциативной памяти. Изложены идеи известных и предложенных в последнее время алгоритмов. Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь и некоторые теоретические аспекты. Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Приведены главным образом индексные структуры на основании разбиения на области (в том числе иерархические) и графов соседства. Обсуждено также ускорение поиска по сходству с использованием преобразования исходных данных. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Проведено сравнение подходов к ускорению поиска по сходству в индексных структурах рассмотренных типов, а также на основе сохраняющего сходство хэширования. Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Приведены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.
 https://doi.org/10.1007/s10559-017-9983-x
 Scopus
Бібліографічний опис:
Рачковский Д. А. Индексные структуры для быстрого поиска по сходству бинарных векторов. Кибернетика и системный анализ. 2017. Т. 53, № 5. С. 167-192. doi: https://doi.org/10.1007/s10559-017-9983-x URL: http://jnas.nbuv.gov.ua/article/UJRN-0000754495 |
 Cybernetics and Systems Analysis / Issue (2017, 53 (5))
Rachkovskij D.A.
Index structures for fast similarity search of binary vectors This article reviews index structures for fast similarity search for objects represented by binary vectors (with components equal to 0 or 1). Structures for both exact and approximate search by Hamming distance and other similarity measures are considered. Mainly., index structures are presented that are based on hash tables and similarity-preserving hashing and also on tree structures, neighborhood graphs, and distributed neural autoassociative memory. Ideas of well-known algorithms and algorithms proposed in recent years are stated. © 2017, Springer Science+Business Media, LLC. Keywords: Hamming distance, index structure, locality-sensitive hashing, multi-index hashing, near neighbor, nearest neighbor, neighborhood graph, neural autoassociative memory, similarity search, tree structure, Bins, Forestry, Hamming distance, Nearest neighbor search, Auto-associative Memory, Index structure, Locality sensitive hashing, Multi-index, near neighbor, Nearest neighbors, Neighborhood graphs, Similarity search, Tree structures, Trees (mathematics)
Cite:
Rachkovskij D.A.
(2017). Index structures for fast similarity search of binary vectors. Cybernetics and Systems Analysis, 53 (5), 167-192. doi: https://doi.org/10.1007/s10559-017-9983-x http://jnas.nbuv.gov.ua/article/UJRN-0000754495 [In Russian]. |
PDF