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

Ключевые слова: поиск по сходству, ближайший сосед, ближний сосед, индексные структуры, метод ветвей и границ, деревья и леса, кластеризация, граф соседства, локально-чувствительное хэширование.