Residual Vector Product Quantization for Approximate Nearest Neighbor Search

Product Quantization is popular for approximate nearest neighbor search, which decomposes the vector space into Cartesian product of several subspaces and constructs separately one codebook for each subspace. The construction of codebooks dominates the quantization error that directly impacts the retrieval accuracy. In this paper, we propose a novel quantization method, residual vector product quantization (RVPQ), which constructs a residual hierarchy structure consisted of several ordered residual codebooks for each subspace. The proposed method minimizes the quantization error by jointly optimizing all the codebooks in each subspace using the efficient mini-batch stochastic gradient descent algorithm. Furthermore, an efficient encoding method, based on H-variable Beam Search, is also proposed to reduce the computation complexity of encoding with negligible loss of accuracy. Extensive experiments show that our proposed method outperforms the-state-of-the-art on retrieval accuracy while retaining a comparable computation complexity.