• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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

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