Anisotropic Additive Quantization for Fast Inner Product Search

Maximum Inner Product Search (MIPS) plays an important role in many applications ranging from information retrieval, recommender systems to natural language processing and machine learning. However, exhaustive MIPS is often expensive and impractical when there are a large number of candidate items. The state-of-the-art approximated MIPS is product quantization with a score-aware loss, which weighs more heavily on items with larger inner product scores. However, it is challenging to extend the score-aware loss for additive quantization due to parallel-orthogonal decomposition of residual error. Learning additive quantization with respect to this loss is important since additive quantization can achieve a lower approximation error than product quantization. To this end, we propose a quantization method called Anisotropic Additive Quantization to combine the scoreaware anisotropic loss and additive quantization. To efficiently update the codebooks in this algorithm, we develop a new alternating optimization algorithm. The proposed algorithm is extensively evaluated on three real-world datasets. The experimental results show that it outperforms the stateof-the-art baselines with respect to approximate search accuracy while guaranteeing a similar retrieval efficiency.

Authors

• Jin Zhang
• Qi Liu
• Defu Lian University of Science and Technology of China
• Zheng Liu
• Le Wu Hefei University of Technology Hefei Comprehensive National Science Center
• Enhong Chen School of Computer Science and Technology, University of Science and Technology of China, Hefei, China State Key Laboratory of Cognitive Intelligence, Hefei, China

Keywords

No keywords are indexed for this paper.