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

Russian (CIS)English (United Kingdom)
 MOSCOW +7(495)-142-86-81

COMPARATIVE ANALYSIS OF GRAPH-BASED NEAREST NEIGHBOR SEARCH ALGORITHMS NSG AND HNSW

Goryachkin Boris Sergeevich  (Candidate of Technical Sciences, Associate Professor Moscow State Technical University named after. N.E. Bauman )

Pavlovskaya Anastasia Andreevna  (Moscow State Technical University named after. N.E. Bauman )

Grigoriev Yuri Alexandrovich  (Doctor of Technical Sciences, Professor Moscow State Technical University named after. N.E. Bauman )

In this paper, two graph-based nearest neighbor search algorithms are discussed: NSG (Navigating spreading-out graph) and HNSW (Hierarchical navigable small world). The relevance of the K-NNS method in modern technologies is substantiated, and specific examples of the application of neighbor search methods are given. Justification for the effectiveness of using graph structures to search for K nearest neighbors is given. Theoretical calculation of the time and volume complexity of the HNSW and HSG algorithms, as well as the quantitative characteristics of the Python implementation, was performed. The obtained theoretical values were confirmed experimentally. It is concluded that NSG is a more reliable algorithm in the case of large data volumes, but it uses more memory for graph construction per stage than HNSW.

Keywords:K-NSS, K nearest neighbors search, graph-based NNS, NSG, Navigating Spreading-out Graph, HNSW, Hierarchical navigable small world.
 

Read the full article …

Citation link:
Goryachkin B. S., Pavlovskaya A. A., Grigoriev Y. A. COMPARATIVE ANALYSIS OF GRAPH-BASED NEAREST NEIGHBOR SEARCH ALGORITHMS NSG AND HNSW // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2024. -№05. -С. 55-65 DOI 10.37882/2223-2966.2024.05.09
LEGAL INFORMATION:
Reproduction of materials is permitted only for non-commercial purposes with reference to the original publication. Protected by the laws of the Russian Federation. Any violations of the law are prosecuted.
© ООО "Научные технологии"

Terms Publications

Issues of the journals (Archive)

ECONOMICS AND LAW
HUMANITIES
NATURAL AND TECHNICAL SCIENCES
COGNITION

Серия - Natural and Technical Sciences