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

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