Revisiting Multi-Codebook Quantization

Xiaosu Zhu, Jingkuan Song, Lianli Gao, Xiaoyan Gu, Hengtao ShenNeurIPS 2021 · OpenReview

Abstract

Multi-Codebook Quantization (MCQ) is a generalized version of existing codebook-based quantizations for Approximate Nearest Neighbor (ANN) search. Therefore, MCQ theoretically has the potential to achieve the best performance because solutions of other codebook-based quantization methods are all covered by MCQ's solution space under the same codebook size setting. However, finding the optimal solution to MCQ is proved to be NP-hard due to its encoding process, \textit{i.e.}, converting an input vector to a binary code. To tackle this, researchers apply constraints to it to find near-optimal solutions, or employ heuristic algorithms which are still time-consuming for encoding. Different from previous approaches, this paper takes the first attempt to find a deep solution to MCQ. The encoding network is designed to be as simple as possible, so the very complex encoding problem becomes simply a feed-forward. Compared with other methods on three datasets, our method shows state-of-the-art performance. Notably, our method is 11×-38× faster than heuristic algorithms for encoding, which makes it more practical for real scenery of large-scale retrieval. Our code is publicly available: https://github.com/DeepMCQ/DeepQ.
BibTeX
@inproceedings{zhu2021revisiting,
  author = {Xiaosu Zhu and Jingkuan Song and Lianli Gao and Xiaoyan Gu and Hengtao Shen},
  title = {{Revisiting Multi-Codebook Quantization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=8jFiomKUnaT},
}

Loading related content...

Figure