Online Variable Coding Length Product Quantization for Fast Nearest Neighbor Search in Mobile Retrieval

Quantization methods are crucial for efficient nearest neighbor search in many applications such as image, music, or product search. As mobile devices are becoming increasingly more popular, the quantization methods on mobile devices are more important, because a large portion of the search queries are becoming performed on mobile devices. One important characteristic of the communication on mobile devices is the inherent unreliability of their communication channels. In order to adapt the quality changes of the communication channels, we need to change the coding length of the quantization accordingly. The existing quantization methods use fixed-length codebooks, and it is expensive to retrain another codebook with different coding length. In this paper, we propose a novel variable length product quantization framework that consists of a set of fast universal scalar quantizers. The framework is capable of producing variable length quantization without retraining the codebook. Each data vector is transformed into a new space to reduce the correlation across dimensions. A proper number of bits is allocated to represent the scalar component in each dimension according to the given coding length. For each component, we estimate its probability density function (PDF) and design an efficient universal scalar quantizer based on the PDF and the allocated bits. To reduce distortion, we learn a Gaussian mixture model for the data. The experimental results show that, compared to state-of-theart product quantization methods, our approach can construct the codebooks online for variable coding lengths and achieve the comparable performance.