Codebook-softened product quantization for high accuracy approximate nearest neighbor search

Product quantization (PQ) is a fundamental technique for approximate nearest neighbor (ANN) search in many applications such as information retrieval, computer vision and pattern recognition. In the existing PQ-based methods for approximate nearest neighbor search, the reachable best search accuracy is achieved by using fixed codebooks. The search performance is limited by the quality of the hard codebooks. Unlike the existing methods, in this paper, we present a novel codebook-softened product quantization (CSPQ) method to achieve more quantization levels by softening codebooks. We firstly analyze how well the database vectors match the trained codebooks by examining quantization error for each database vector, and select the bad-matching database vectors. Then, we give the trained codebooks bbit freedom to soften codebooks. Finally, by minimizing quantization errors, the bad-matching vectors are encoded by softened codebooks and the labels of best-matching codebooks are recorded. Experimental results on SIFT1M, GIST1M and SIFT10M show that, despite its simplicity, our proposed method achieves higher accuracy compared with PQ and it can be combined with other nonexhaustive frameworks to achieve fast search. (c) 2022 Elsevier B.V. All rights reserved.