інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0001018674
Кибернетика и системный анализ   А - 2019 /  Випуск (2019, Т. 55, № 5)
Рачковский Д. А.
Индексные структуры для быстрого поиска сходных символьных строк Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Приведены, главным образом, индексные структуры на основе хэш-таблиц, сохраняющего сходство хэширования, а также древовидных структур, графов соседства и нейросетевой распределенной автоассоциативной памяти. Изложены идеи известных и предложенных в последнее время алгоритмов. Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены индексные структуры на основе локально-чувствительного хэширования и их модификации. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Обсуждена их взаимосвязь и некоторые теоретические аспекты. Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных вещественными векторами. Рассмотрены структуры как для точного, так и для более быстрого, но приближенного поиска. Приведены главным образом индексные структуры на основании разбиения на области (в том числе иерархические) и графов соседства. Обсуждено также ускорение поиска по сходству с использованием преобразования исходных данных. Изложены идеи конкретных алгоритмов, включая недавно предложенные. Проведено сравнение подходов к ускорению поиска по сходству в индексных структурах рассмотренных типов, а также на основе сохраняющего сходство хэширования. Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных символьными строками. Рассмотрены индексные структуры как для точного, так и для приближенного поиска по расстоянию редактирования. Приведены индексные структуры на основе обратного индексирования, сохраняющего сходство хэширования, древовидных структур. Изложены идеи известных и предложенных в последнее время алгоритмов.
 https://doi.org/10.1007/s10559-019-00196-7
 Scopus
Бібліографічний опис:
Рачковский Д. А. Индексные структуры для быстрого поиска сходных символьных строк. Кибернетика и системный анализ. 2019. Т. 55, № 5. С. 180-202. doi: https://doi.org/10.1007/s10559-019-00196-7 URL: http://jnas.nbuv.gov.ua/article/UJRN-0001018674 |
 Cybernetics and Systems Analysis / Issue (2019, 55 (5))
Rachkovskij D.A.
Index structures for fast similarity search for symbolic strings This article surveys index structures for fast similarity search for objects represented by symbol strings. Index structures both for exact and approximate searches by edit distance are considered. Index structures based on inverted indexing, similarity preserving hashing, and treelike structures are mainly presented. Ideas of well-known and recently proposed algorithms are described. © 2019, Springer Science+Business Media, LLC, part of Springer Nature. Keywords: edit distance, index structure, inverted indexing, locality-sensitive hashing, n-gram, near neighbor, nearest neighbor, similarity search, treelike structure, Forestry, Indexing (of information), Edit distance, Index structure, Inverted indexing, Locality sensitive hashing, N-grams, near neighbor, Nearest neighbors, Similarity search, Tree-like structures, Nearest neighbor search
Cite:
Rachkovskij D.A.
(2019). Index structures for fast similarity search for symbolic strings. Cybernetics and Systems Analysis, 55 (5), 180-202. doi: https://doi.org/10.1007/s10559-019-00196-7 http://jnas.nbuv.gov.ua/article/UJRN-0001018674 [In Russian]. |
PDF