Сравнительный анализ структур данных для приближенного поиска ближайшего соседа
Пономаренко Александр Александрович
старший преподаватель кафедры "Прикладная математика и информатика", ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики», г. Нижний Новгород.
Аврелин Никита Сергеевич
магистрант кафедры "Прикладная математика и информатика", ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики», г. Нижний Новгород.
Найдан Билэгсайхан
аспирант кафедры "Прикладная математика и информатика", ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики», г. Нижний Новгород.
Бойцов Леонид Моисеевич
аспирант кафедры "Прикладная математика и информатика", ФГАОУ ВПО «Национальный исследовательский университет «Высшая школа экономики», г. Нижний Новгород.
Аннотация:
Поиск по похожести широко применяется в различных областях компьютерных наук. Множество методов было предложено для решения задачи в точной постановке, однако все они подвержены "проклятью" размерности и не эффективны для данных высокой размерности. Приближенные алгоритмы отчасти позволяют справиться с "проклятьем". Однако из-за сложной стохастической природы, теоретические оценки для большинства приближенных алгоритмов отсутствуют. Более того, на данный момент времени, в литературе не существует работ, включающих всесторонний эмпирический анализ современных методов для поиска по подобию. Как правило, авторы алгоритмов ограничиваются небольшими численными экспериментами, сравнивая свой алгоритм с одним ранее известным методом. С целью устранения этого пробела в научном знании, в настоящей работе мы приводим результаты такого эмпирического анализа для методов: Vantage Point Tree, Locality Sensitive Hashing, List of Clusters, Метризованный Тесный Мир и несколько вариаций Permutation Index. Проведенные эксперименты показывают, что Метризованный Тесный Мир имеет наилучшее соотношение между вычислительной сложностью и точностью, как для метрических, так и для не метрическихй пространств.
Ключевые слова:
поиск ближайшего соседа, метрическое пространство, неметрический поиск, приближенный поиск, графы тесного мира.
Шифры классификации:
УДК: 004.043, 004.057.4
ГРНТИ: 20.23.19
ВАК: 05.13.01
