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

Jin Li, Xuguang Lan, Xiangwei Li, Jiang Wang, Nanning Zheng, Ying Wu

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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-the-art product quantization methods, our approach can construct the codebooks online for variable coding lengths and achieve the comparable performance.

Original languageEnglish (US)
Article number7589007
Pages (from-to)559-570
Number of pages12
JournalIEEE Transactions on Multimedia
Issue number3
StatePublished - Mar 2017


  • Approximate nearest neighbor search
  • Gaussian mixture model
  • low-complexity quantizer design
  • variable coding length

ASJC Scopus subject areas

  • Signal Processing
  • Media Technology
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Online Variable Coding Length Product Quantization for Fast Nearest Neighbor Search in Mobile Retrieval'. Together they form a unique fingerprint.

Cite this