Research On Nearest Neighbor Search Method Based On Multi-stage Vector Quantization

With the development of Internet technology,in different industries and fields,various types of data such as voice,image and video continue to increase.The retrieval of massive highdimensional data has become one of the most important research topics,simultaneously,it is the research direction that scholars focus on.In actual information retrieval applications,the approximate nearest neighbor search method based on vector quantization is one of the most commonly used techniques to reduce the memory overhead in the indexing process.The vector quantization method greatly reduces the memory storage of high-dimensional data by encoding the dataset vector efficiently and compactly;In the case of sacrificing the accuracy of the acceptable range,the approximate nearest neighbor search method returns the data similar to the target query data,and the results are as accurate as possible.This method could speed up the data retrieval speed and improve the data retrieval efficiency.In recent years,many scholars have proposed some approximate nearest neighbor methods based on vector quantization,such as product quantization algorithm,optimized product quantization algorithm and multi-stage vector quantization algorithm.Among these methods,the multi-stage vector quantization algorithm uses multiple low-complexity vector quantizers to retain the vector quantization error generated in the current stage,and use it as the input vector of the next stage vector quantizer.Then quantify it to reduce the vector quantization error gradually step by step.Therefore,this method improves the quantization result of the vector and the query accuracy of the data.This paper proposes a multi-path collaborative coding vector quantization algorithm based on multi-stage vector quantization algorithm,with the goal of minimizing the vector quantization error.The training codebook process and the vector coding process in this method are studied respectively.In the process of training the codebook,in order to optimize the initial clustering center,the data points that are far away from each other are selected as the initial clustering center,which improves the quality of the corresponding codebook at each stage,and makes the reconstructed vector more precise.In the vector coding process,in view of the local optimization problem of vector coding,this paper proposes a multi-path collaborative coding strategy.When reaching a certain data point in each stage,delete the coding path that does not meet the minimum quantization error requirements.Each stage maintains a certain number of coding paths,and finally selects an optimal coding path as the vector coding,which can achieve approximate global optimal results.In terms of efficiency,this strategy reduces computational complexity;in terms of accuracy,this strategy further reduces the quantization error of vector coding.This paper conducts experiments and analyses on the public datasets such as SIFT1 M and GIST1 M.Then compares the results of the proposed method from different performance indicators,such as vector quantization error,query recall rate,etc.The experimental results show that the multipath collaborative coding vector quantization algorithm proposed in this paper can obtain a more accurate codebook and approximate the global optimal encoding of the vector,therefore it further reduce the vector quantization error and improve the query recall rate.In addition,this paper compares the multi-path collaborative coding vector quantization algorithm with some common vector quantization methods,which shows that this method has a larger performance advantage.In addition,these experiments further prove that the algorithm is effective and feasible.