Research On Approximate Nearest Neighbor Search Algorithm Based On Graph

With the rapid development of the Internet,a huge amount of multimedia information has been generated,which places higher requirements on data mining technology.Approximate nearest neighbor(ANN),as a basic problem in data mining,is also a hot issue.It aims to quickly retrieve the most similar data from massive data.However,with the increase of the data dimension,the retrieval speed and accuracy of traditional tree-based retrieval methods and hash-based retrieval methods can no longer meet the requirements.At present,the graph-based retrieval method has a good performance.In this paper,the graph-based retrieval method is researched in depth to improve the efficiency of neighbor search.This paper proposes a method of quickly dividing the data first,and then mapping the cluster center,which can significantly reduce the index construction time and reduce the index structure.In order to improve the quality of the graph index,a new graph index is created on the pre-built knn graph,and the knn graph is gradually replaced with the new graph index,which can improve the retrieval accuracy and shorten the retrieval path,so that the retrieval speed can be improve.Using the method of second-line quantization,the original vector is quantized to reduce the memory space occupation and the calculation complexity of the distance between the vectors,and the calculation without relying on the query vector can be calculated in advance to improve the speed of retrieval.The test results on different datasets show that the algorithm designed in this paper can guarantee high retrieval accuracy,at the same time,the retrieval speed is faster and the index structure is smaller.Compared with hierarchcal navigable small world graphs algorithm,the query time of sift1 m dataset is reduced by 30% under the same precision,and the index structure is reduced by 45%.