Approximate nearest neighbor search by cyclic hierarchical product quantization

Abstract

Vector quantization (VQ) is a widely used Approximate Nearest Neighbor (ANN) search method. By constructing multiple codebooks, VQ can create more codeword vectors with lower memory consumption, enabling the indexing of large-scale database. In recent years, many VQ-based methods have been proposed, but the codeword vectors constructed in these methods are often underutilized due to insufficient data support, and the unimodal data distribution within the partition is not considered. To address these issues, we propose a new quantization method, Cyclic Hierarchical Product Quantization (CHPQ). This method first constructs a hierarchical quantization structure in each subspace, with each hierarchical structure composed of several sub-quantizers. Then, the codebook is locally optimized under the sub-quantizers according to the data distribution of each Voronoi cell, significantly improving quantization performance compared to other methods and greatly enhancing the accuracy of ANN search. Additionally, this paper proposes a new hierarchical quantization structure, termed cyclic hierarchical structure, which can generate more diverse codeword vectors in different space partitions compared to the traditional hierarchical quantization structure. Experiment results demonstrate that CHPQ outperforms existing methods in terms of retrieval accuracy while maintaining comparable computational efficiency.