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

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