Quantization based Fast Inner Product Search

By Ruiqi Guo, Sanjiv Kumar, Krzysztof Marcin Choromanski, David Simcha. 2015

117 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Information Systems, Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Information Systems

In Information Retrieval & Search

Citations in the corpus

Learning Dense Representations for Entity Retrieval (2019, positive): “To estimate performance in a real-world setting, we repeat the evaluation of DEER using the quantization-based approaches described by Guo et al. (2016).”
Efficient Natural Language Response Suggestion for Smart Reply (2017, methodology): “For more background, we refer readers to the relevant works of [3, 5, 21, 22].”
The Web Is Your Oyster - Knowledge-Intensive NLP against a Very Large Web Corpus (2021, methodology): “Efﬁcient dense retrieval is enabled by maximum inner product search algorithms (Shri-vastava and Li, 2014; Guo et al., 2015) leveraged by tools like FAISS (Johnson et al., 2017 Although Australia sadly ended up as one of this year's biggest flops (currently at $39 million), filmmaker Baz Luhrmann…”
Sparse, Dense, and Attentional Representations for Text Retrieval (2020, background): “The size of the index must grow by a factor of m, but due to the efficiency of contemporary approximate nearest neighbor and maximum inner product search, the time complexity can be sub-linear (Andoni et al., 2019; Guo et al., 2016).”
Pre-training Tasks for Embedding-based Large-scale Retrieval (2020, methodology): “Since the embeddings of all candidate documents can be pre-computed and indexed, the inference can be done efﬁciently with approximate nearest neighbor search algorithms in the embedding space (Shrivastava & Li, 2014; Guo et al., 2016).”
End-to-End Retrieval in Continuous Space (2018, methodology): “First, a simple quantization method (Guo et al., 2016) works quite well for the tasks we consider; second, since we are more interested in analyzing modeling issues, we use exhaustive search to avoid any confounding effects linked to the choice of approximate search algorithm.”
Multi-Task Retrieval for Knowledge-Intensive Tasks (2021, methodology): “Efﬁ-cient index and search of dense vectors are made possible by maximum inner product search (MIPS) algorithms (e.g., Shrivastava and Li, 2014; Guo et al., 2016), as well as tools like FAISS (Johnson et al., 2019).”
Length bias in Encoder Decoder Models and a Case for Global Conditioning (2016, methodology): “WhenW is very large, we can obtain an approximate solution by indexing the vectors vy of W using recent methods specifically designed for dot-product based retrieval (Guo et al., 2016).”
Factorized Deep Retrieval and Distributed TensorFlow Serving (2018, background): “Specifically, compact representation of high dimensional embeddings are built through quantization [5] and end-to-end learning of coarse and product quantizers [12].”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “The vector quantization can thus be used to obtain a “residual dataset” with much smaller diameter, yielding significant reductions in quantization error when quantized with only a product code [15].”
Sampling-bias-corrected neural modeling for large corpus item recommendations (2019, background): “Specifcally, compact representations of high dimensional embeddings are built through quantization [20] and end-to-end learning of coarse and product quantizers [36].”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, methodology): “We compare to LSQ (Martinez et al., 2018) and all three variants of QUIPS (Guo et al., 2016b).”
Top-K Off-Policy Correction for a REINFORCE Recommender System (2018, methodology): “e the full softmax, which is prohibitively expensive considering our action space. Rather, we make use of efficient approximate nearest neighbor-based systems to look up the top �items in the softmax [14]. We then feed the logits of these �items into a smaller softmax to normalize the probabilities ”
Clustering is Efficient for Approximate Maximum Inner Product Search (2015, background): “Finally, we mention that, while putting the final touches to this paper, another very recent and different MIPS approach, based on vector quantization, came to our knowledge (Guo et al., 2015).”