Pyramid Product Quantization for Approximate Nearest Neighbor Search

Product quantization (PQ) is a widely adopted technique for efficient approximate nearest neighbor (ANN) search in high-dimensional spaces, offering a favorable balance between accuracy and memory efficiency. However, standard PQ suffers from high online computational cost when the number of subspaces is high. To address this dilemma, we propose Pyramid Product Quantization (PPQ), a novel adaptive quantization framework that dynamically selects the most suitable number of subspaces for different segments of each data vector. This leads to a significant reduction in the number of addition operations required during approximate distance computation, significantly accelerating online search. Experimental results demonstrate that the proposed PPQ method effectively lowers the computational complexity of product quantization and its variants, without compromising retrieval accuracy.