Local Deep Learning Quantization for Approximate Nearest Neighbor Search

Product quantization (PQ) is an effective vector quantization approach to compactly encode high-dimensional vectors for approximate nearest neighbor search (ANNS). While the PQ-based ANNS methods achieve remarkable time and space efficiency, their search accuracy falls short. The main reason is the excessive quantization error of vectors used for similarity computation during the search phase. We refer to the set of these computed vectors as the local range set. We observe that if the vectors in the local range set are optimally ranked, the search accuracy will be significantly improved. Based on this observation, we propose a Local Deep Learning Quantization (LDLQ) framework. This framework involves mapping codewords to fake vectors within the local range set and utilizes fake vectors for ranking. Experimental results demonstrate that the LDLQ framework significantly improves the accuracy of existing PQ-based ANNS methods while maintaining low computation and space overhead. Notably, our method can be plugged into existing PQ-based approaches for performance enhancement, making it versatile and widely deployable.