СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТРУКТУР ДАННЫХ ДЛЯ ПРИБЛИЖЕННОГО ПОИСКА БЛИЖАЙШЕГО СОСЕДА

Алгоритмы, методы и системы обработки данных. 2015. Т. 4. № 33. С. 91–106.

Пономаренко А. А., Аврелин Н. С., Найдан Б. С., Бойцов Л. М.

Поиск по похожести широко применяется в различных областях компьютерных наук. Множество методов было предложено для решения задачи в точной постановке, однако все они подвержены "проклятью" размерности и не эффективны для данных высокой размерности. Приближенные алгоритмы отчасти позволяют справиться с "проклятьем". Однако из-за сложной стохастической природы, теоретические оценки для большинства приближенных алгоритмов отсутствуют. Более того, на данный момент времени, в литературе не существует работ, включающих всесторонний эмпирический анализ современных методов для поиска по подобию. Как правило, авторы алгоритмов ограничиваются небольшими численными экспериментами, сравнивая свой алгоритм с одним ранее известным методом. С целью устранения этого пробела в научном знании, в настоящей работе мы приводим результаты такого эмпирического анализа для методов: Vantage Point Tree, Locality Sensitive Hashing, List of Clusters, Метризованный Тесный Мир и несколько вариаций Permutation Index. Проведенные эксперименты показывают, что Метризованный Тесный Мир имеет наилучшее соотношение между вычислительной сложностью и точностью, как для метрических, так и для неметрических пространств.

Ключевые слова: сравнительный анализ, метрическое пространство, comparative analysis, Approximate Nearest Neighbor, nearest neighbor search, поиск ближайшего соседа, Algorithms and data structures, Алгоритмы и структуры данных