Study Of Vector Quantization Based Approximate Nearest Neighbor Search

With the explosive growth of multimedia data,the scale and dimension of data are increasing.And the nearest neighbor search based on original data no longer satisfy the requirements of practical tasks in terms of memory and efficiency.Therefore,the more feasible approximate nearest neighbor search methods are becoming more and more significant.However,as one of the best techniques for approximate nearest neighbor search,vector quantization still can not strike the balance between speed and accuracy,and the integration with inverted index can also be improved.Based on the vector quantization,in this paper,the current vector quantization methods are improved from two aspects which respectively are quantization structure and index structure,in order to enhance the performance of the approximate nearest neighbor search.The main contributions of this paper are concluded as follows.(1)Product Quantization is popular for approximate nearest neighbor search,which decomposes the vector space into Cartesian product of several subspaces.However,PQ only constructs one codebook for each subspace,thus limiting the quantization error that can directly impact the retrieval accuracy.In this paper,a novel quantization method,residual vector product quantization,is proposed.This method constructs a residual hierarchy structure consisted of several residual codebooks for each subspace,and all codebooks of a subspace are trained based on joint optimization strategy.Furthermore,an efficient encoding method is also proposed to reduce the computation complexity of encoding without negligible losing accuracy.Theoretical analysis and experiments on SIFT-1M and GIST-1M show that the proposed method outperforms the-state-of-the-art methods while retaining a comparable computation complexity.(2)Inverted Multi Index and the standard Inverted Index are very popular and efficient approximate nearest neighbor search framework,which can transform the exhaustive search into non-exhaustive search.In this paper,the proposed Residual Vector Product Quantization is combined with the Inverted Multi Index to design an efficient non-exhaustive retrieval system.In addition,in order to improve the location efficiency of subregions of the standard Inverted Index,the Product Quantization is used to quantize the inverted indices of subregions,and then the lookup table technique of PQ can be utilized to accelerate the distance computation between the query and indices of subregions.Therefore,the efficiency of nonexhaustive search system based on inverted index is improved.Experiment on SIFT-10 M dataset shows that the proposed non-exhaustive search systems can effectively solve the large-scale data based approximate nearest neighbor search tasks.