Iteratively Multiple Projections Optimization for Product Quantization in Nearest Neighbor Search

Recently, the variable length coding product quantization is proposed to accelerate the speed of codebook training for approximate nearest neighbor (ANN) search. And the Gaussian Mixture model (GMM) is trained as a coarse quantizer to project the data into different subspaces respectively. However, the existing method trains the GMM without considering the quantization distortion. In this paper, we propose a novel distortion model which can jointly train the multiple projections and fine quantizers. Based on the loss function, multiple projected matrixes, quantizer of each subspace and the partition of the training set are optimized iteratively. Moreover, the solution of the problem is further analyzed and a simpler form for training is derived. The experimental results verify the improvements when the spaces decomposition and the quantizers are optimized jointly.