Revisiting Multi-Codebook Quantization
Lists
Only you see this
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...