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

Goryachkin Boris Sergeevich, Pavlovskaya Anastasia Andreevna, Grigoriev Yuri Alexandrovich

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.