Optimized Product Quantization for Approximate Nearest Neighbor Search

摘要: Product quantization is an effective vector approach to compactly encode high-dimensional vectors for fast approximate nearest neighbor (ANN) search. The essence of product decompose the original space into Cartesian a finite number low-dimensional subspaces that are then quantized separately. Optimal decomposition important performance ANN search, but still remains unaddressed. In this paper, we optimize by minimizing distortions w.r.t. and codebooks. We present two novel methods optimization: non-parametric method alternatively solves smaller sub-problems, parametric guaranteed achieve optimal solution if input data follows some Gaussian distribution. show experiments our optimized substantially improves accuracy