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

Abstract

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

Наведено огляд індексних структур для швидкого пошуку за схожістю об’єктів, що представлені дійсними векторами. Розглянуто індексні структури на основі локально-чутливого хешування та їхні модифікації. Викладено ідеї конкретних алгоритмів (відомих та нещодавно запропонованих). Обговорено їхній взаємозв’язок і деякі теоретичні аспекти.

In this survey paper, we consider index structures for fast similarity search of objects represented by real-valued vectors. Index structures based on locality-sensitive hashing and their modifications are considered. The ideas of specific algorithms, including the recently proposed ones, are outlined. Their interrelations and some theoretical aspects are discussed.