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

Ключові слова: відстань, схожість, вкладення, скетчі, зниження розмірності, випадкові проеціювання, семпліювання, лема Джонсона–Лінденштрауса, ядерна схожість, пошук за схожістю.