Revisiting Multi-Codebook Quantization

Xiaosu Zhu

doi:10.1109/TIP.2023.3261755

2023-01-01

PRE

Xiaosu Zhu

Jingkuan Song (Jingkuan Song) *

Lianli Gao

顾小燕 (Xiaoyan Gu)

申恒涛 (Heng Tao Shen)

DOI：10.1109/TIP.2023.3261755

原文链接

原文求助

摘要

En 中文

Multi-Codebook Quantization (MCQ) is a generalized version of existing codebook-based quantizations for Approximate Nearest Neighbor (ANN) search. Specifically, MCQ picks one codeword for each sub-codebook independently and takes the sum of picked codewords to approximate the original vector. The objective function involves no constraints, 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, 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 that 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\times $ - $38\times $ faster than heuristic algorithms for encoding, which makes it more practical for the real scenery of large-scale retrieval. Our code is publicly available: https://github.com/DeepMCQ/DeepQ.

Keyword:

Quantization (signal)

Encoding

Training

Image coding

Neural networks

Clustering algorithms

Approximation algorithms

Multi-codebook quantization

approximate nearest neighbor search

retrieval