| In recent years,with the rapid development of the internet and multimedia,the demand of people for information retrieval is also significantly increasing.As a basic data structure in information retrieval,the k-nearest neighbor(k-NN)graph has been widely used in approximate NN search algorithms.Despite their great success,existing graph construction algorithms still mainly focus on building an approximate k-NN graph for a fixed dataset,which limits the k-NN graph to be built incrementally and applied to a larger dataset.Moreover,the k-NN graph merge problem is usually ignored since it is hard to be solved.Based on the above issues,this thesis focuses on the k-NN graph merge problem,and further shows the application of the merge algorithm in the approximate nearest neighbor search.To sum up,this thesis makes the following contributions:(1)Firstly,two generic and efficient k-NN graph merge algorithms are proposed.Based on the nearest neighbor descent(NN-Descent),the proposed algorithms not only leverages the information of existing nearest neighbor graph but also efficiently decrease the number of distance comparisons,thus leading to significant performance improvement.More specifically,we firstly propose a novel Symmetric Merge(SMerge)algorithm to effectively merge two existing k-NN graphs.Note that the proposed S-Merge is essential and it plays a key role in parallel approximate k-NN graph construction.To further address the issue of adding a raw sample set into an already built k-NN graph,a Joint Merge(J-Merge)algorithm is presented.We show that our J-Merge is suitable for building an approximate k-NN graph for an open set.Theoretical analysis and experimental results demonstrate that the time complexity of these two merge algorithms is approximately 25%～75%of NN-Descent.(2)Moreover,to alleviate the main limitations in existing approximate NN search,this thesis presents a new hierarchical graph construction algorithm(H-Merge)based on the proposed J-Merge.H-Merge takes advantage of the J-Merge,and can effectively support index maintenance on data increments.Meanwhile,this thesis further applies the hierarchical search strategy to H-Merge,which facilitates fast NN search.Experimental results demonstrate that the NN search of the proposed algorithm can achieve good performance.(3)Finally,in order to further analyze the approximate NN search based on the NN graph,this thesis conducts comprehensive studies.The role of three major impact factors,namely graph quality,graph diversification and graph hierarchy that are applied for these algorithms are investigated.Considering the wide usage of these algorithms,the experiments in this part can be a good reference for the following related research. |
