Журнал «Современная Наука»

СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА БЛИЖАЙШИХ СОСЕДЕЙ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ 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

Читать полный текст статьи …

Ссылка для цитирования:
Горячкин Б. С., Павловская А. А., Григорьев Ю. А. СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА БЛИЖАЙШИХ СОСЕДЕЙ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ NSG И HNSW // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2024. -№05. -С. 55-65 DOI 10.37882/2223-2966.2024.05.09

ПРАВОВАЯ ИНФОРМАЦИЯ:
Перепечатка материалов допускается только в некоммерческих целях со ссылкой на оригинал публикации. Охраняется законами РФ. Любые нарушения закона преследуются в судебном порядке.
© ООО "Научные технологии"