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

• Published in: Кибернетика и системный анализ
• Date: 2017
• Main Author: Рачковский, Д.А.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2017
• Subjects: Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/144801
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Индексные структуры для быстрого поиска по сходству бинарных векторов / Д.А. Рачковский // Кибернетика и системный анализ. — 2017. — Т. 53, № 5. — С. 167–192. — Бібліогр.: 134 назв. — рос.

Дан обзор индексных структур для быстрого поиска по сходству объектов, представленных бинарными векторами (с компонентами 0 или 1). Рассмотрены структуры как для точного, так и для приближенного поиска по расстоянию Хэмминга и другим мерам сходства. Представлены, главным образом, индексные структуры на основе хэш-таблиц, сохраняющего сходство хэширования, а также древовидных структур, графов соседства и нейросетевой распределенной автоассоциативной памяти. Изложены идеи известных и предложенных в последнее время алгоритмов. Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені бінарними векторами (із компонентами 0 або 1). Розглянуто структури як для точного, так і для наближеного пошуку за відстанню Хеммінга та іншими мірами схожості. Описано, головним чином, індексні структури на основі хеш-таблиць, хешування, що зберігає схожість, а також деревовидних структур, графів сусідства та нейромережевої розподіленої автоасоціативної пам’яті. Викладено ідеї конкретних алгоритмів (відомих та нещодавно запропонованих). We survey index structures for fast similarity search of objects represented by binary vectors (with components 0 or 1). Structures for both exact and approximate search by Hamming distance and other similarity measures are considered. Mainly, we present index structures based on hash tables, similarity-preserving hashing, as well as tree structures, neighborhood graphs, and neural distributed autoassociative memory. The ideas of specific algorithms, including the recently proposed ones, are outlined.