СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА БЛИЖАЙШИХ СОСЕДЕЙ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ NSG И HNSW

Горячкин Борис Сергеевич, Павловская Анастасия Андреевна, Григорьев Юрий Александрович

В данной работе рассмотрены два алгоритма поиска ближайших соседей с использованием графов: NSG (Navigating Spreading-out Graph) и HNSW (Hierarchical navigable small world). Обоснована актуальность метода поиска ближайших соседей в современных технологиях, приведены конкретные примеры применения алгоритмов поиска соседей. Приводится обоснование эффективности применения графовых структур для поиска K ближайших соседей. Выполнен теоретический расчет временной и емкостной сложности алгоритмов HNSW и HSG, а также количественных характеристик конкретной реализации на Python. Полученные теоретические значения были подтверждены экспериментально. Был сделан вывод о том, что NSG является более предпочтительным вариантом в случае больших объемов данных, но использует больше памяти для стадии построения графа, чем HNSW.

Ключевые слова:K-NSS, поиск K ближайших соседей, основанные на графах методы поиска ближайших соседей, NSG, Navigating Spreading-out Graph, HNSW, Hierarchical navigable small world