Quantization based Fast Inner Product Search

Abstract

We propose a quantization based approach for fast approximate Maximum Inner Product Search (MIPS). Each database vector is quantized in multiple subspaces via a set of codebooks, learned directly by minimizing the inner product quantization error. Then, the inner product of a query to a database vector is approximated as the sum of inner products with the subspace quantizers. Different from recently proposed LSH approaches to MIPS, the database vectors and queries do not need to be augmented in a higher dimensional feature space. We also provide a theoretical analysis of the proposed approach, consisting of the concentration results under mild assumptions. Furthermore, if a small sample of example queries is given at the training time, we propose a modified codebook learning procedure which further improves the accuracy. Experimental results on a variety of datasets including those arising from deep neural networks show that the proposed approach significantly outperforms the existing state-of-the-art.

References in corpus (2)

• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
• On Symmetric and Asymmetric LSHs for Inner Product Search

Cited by in corpus (17)

• Efficient Natural Language Response Suggestion for Smart Reply
• Sparse, Dense, and Attentional Representations for Text Retrieval
• End-to-End Retrieval in Continuous Space
• Now Playing: Continuous low-power music recognition
• Foundations of Vector Retrieval
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering
• Revisiting Neural Retrieval on Accelerators
• Leveraging Semantic and Lexical Matching to Improve the Recall of Document Retrieval Systems: A Hybrid Approach
• Stochastic Generative Hashing
• Top-K Off-Policy Correction for a REINFORCE Recommender System
• Efficient Inner Product Approximation in Hybrid Spaces
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
• SAH: Shifting-aware Asymmetric Hashing for Reverse $k$-Maximum Inner Product Search
• Neural Naturalist: Generating Fine-Grained Image Comparisons
• Climbing the WOL: Training for Cheaper Inference
• Linear Bandit Algorithms with Sublinear Time Complexity
• ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index