Approximate nearest neighbor algorithm based on navigable small world graphs

作     者：Malkov, Yury Ponomarenko, Alexander Logvinov, Andrey Krylov, Vladimir 

作者机构：Russian Acad Sci Inst Appl Phys Nizhnii Novgorod 603950 Russia MERA Labs LLC Nizhnii Novgorod 603163 Russia Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Network Anal Nizhnii Novgorod 603093 Russia Nizhnii Novgorod State Tech Univ Nizhnii Novgorod Russia 

出 版 物：《INFORMATION SYSTEMS》 (信息系统)

年 卷 期：2014年第45卷

页      面：61-68页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Similarity search k-Nearest neighbor Approximate nearest neighbor Navigable small world Distributed data structure 

摘      要：We propose a novel approach to solving the approximate k-nearest neighbor search problem in metric spaces. The search structure is based on a navigable small world graph with vertices corresponding to the stored elements, edges to links between them, and a variation of greedy algorithm for searching. The navigable small world is created simply by keeping old Delaunay graph approximation links produced at the start of construction. The approach is very universal, defined in terms of arbitrary metric spaces and at the same time it is very simple. The algorithm handles insertions in the same way as queries: by finding approximate neighbors for the inserted element and connecting it to them. Both search and insertion can be done in parallel requiring only local information from the structure. The structure can be made distributed. The accuracy of the probabilistic k-nearest neighbor queries can be adjusted without rebuilding the structure. The performed simulation for data in the Euclidean spaces shows that the structure built using the proposed algorithm has small world navigation properties with log(2)(n) insertion and search complexity at fixed accuracy, and performs well at high dimensionality. Simulation on a CoPHiR dataset revealed its high efficiency in case of large datasets (more than an order of magnitude less metric computations at fixed recall) compared to permutation indexes. Only 0.03% of the 10 million 208-dimensional vector dataset is needed to be evaluated to achieve 0.999 recall (virtually exact search). For recall 0.93 processing speed 2800 queries/s can be achieved on a dual Intel X5675 Xenon server node with Java implementation. (C) 2013 Elsevier Ltd. All rights reserved.