Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

By Anshumali Shrivastava, Ping Li. 2014

508 citations recorded by the source corpus.

We present the first provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS). Our proposal is also the first hashing algorithm for searching with (un-normalized) inner product as the underlying similarity measure. Finding hashing schemes for MIPS was considered hard. We formally show that the existing Locality Sensitive Hashing (LSH) framework is insufficient for solving MIPS, and then we extend the existing LSH framework to allow asymmetric hashing schemes. Our proposal is based on an interesting mathematical phenomenon in which inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search. This key observation makes efficient sublinear hashing scheme for MIPS possible. In the extended asymmetric LSH (ALSH) framework, we provide an explicit construction of provably fast hashing scheme for MIPS. The proposed construction and the extended LSH framework could be of independent theoretical interest. Our proposed algorithm is simple and easy to implement. We evaluate the method, for retrieving inner products, in the collaborative filtering task of item recommendations on Netflix and Movielens datasets.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Signal Processing

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

REALM: Retrieval-Augmented Language Model Pre-Training (2020, methodology): “Thus, we can employ Maximum Inner Product Search (MIPS) algorithms to find the approximate top k documents, using running time and storage space that scale sub-linearly with the number of documents (Ram & Gray, 2012; Shrivastava & Li, 2014; Shen et al., 2015).”
Entities as Experts: Sparse Memory Access with Entity Supervision (2020, background): “, 2019) and, while our current implementation does not yet include an efficient implementation of top-k routing (Section 2), we note that it is possible with fast maximum inner product search (Ram and Gray, 2012; Shen et al., 2015; Shrivastava and Li, 2014; Johnson et al., 2017).”
Efficient Natural Language Response Suggestion for Smart Reply (2017, methodology): “The curve is produced by varying the number of approximate neighbors retrieved by our hierarchical quantization method and by Asymmetric LSH [22], and varying the number of leaves searched by the clustering algorithm of [3].”
Quantization based Fast Inner Product Search (2015, methodology): “Shrivastava and Li [18] showed that when m → ∞, MIPS in the original space is equivalent to L2NNS in the new space.”
The Web Is Your Oyster - Knowledge-Intensive NLP against a Very Large Web Corpus (2021, methodology): “2 Efficient dense retrieval is made possible by maximum inner product search algorithms (Shrivastava and Li, 2014; Guo et al., 2015) leveraged by tools like FAISS (Johnson et al.”
SELFEXPLAIN: A Self-Explaining Architecture for Neural Text Classifiers (2021, methodology): “MIPS can often be efficiently scaled using approximate algorithms (Shrivastava and Li, 2014) For the GIL layer, we aggregate the scores over all the retrieved q1:K as a weighted sum, followed by an activation layer, linear layer and softmax to compute the log-likelihood loss as follows:”
FastText.zip: Compressing text classification models (2016, methodology): “Several approaches derived from LSH have been recently proposed to achieve this goal, such as Asymmetric LSH by Shrivastava & Li (2014), subsequently discussed by Neyshabur & Srebro (2015).”
Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language (2022, methodology): “Those include pruning and various indexing techniques, such as LSH-hashing (Shrivastava and Li 2014).”
A Hierarchical Recurrent Encoder-Decoder for Generative Context-Aware Query Suggestion (2015, background): “In the future, the computational cost may be greatly reduced by employing locality sensitive hashing (LSH) based techniques [37].”
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 Training of Neural Retrievers for Open-Domain Question Answering (2021, methodology): “We therefore did not optimize or approximate the similarity search using LSH (Andoni et al., 2015) or efﬁcient maximum inner product search (Shrivastava and Li, 2014).”
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).”
Differentiable Reasoning over a Virtual Knowledge Base (2020, methodology): “This can be done efﬁciently using approximate algorithms (Shrivastava & Li, 2014).”
BlackOut: Speeding up Recurrent Neural Network Language Models With Very Large Vocabularies (2015, methodology): “…2008); Jean et al. (2015), and the use of NCE (Gutmann & Hyv¨arinen, 2012) in Mnih & Teh (2012) all fall under this category, so does the more recent use of Locality Sensitive Hashing (LSH) techniques (Shrivastava & Li, 2014; Vi-jayanarasimhan et al., 2014) to select a subset of good samples.”
RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering (2020, methodology): “act maximum inner product search (Shrivastava and Li, 2014), and we use the implementation of FAISS (Johnson et al.”
Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, methodology): “Definition [23]: (AsymmetricLocality Sensitive Hashing (ALSH)) A family H, along with the two vector functionsQ ∶ R ↦ RD′ (Query Transformation ) andP ∶”
SPARTA: Efficient Open-Domain Question Answering via Sparse Transformer Matching Retrieval (2020, methodology): “Approximate nearest neighbor (ANN) search is then used to enable real-time retrieval for large dataset (Shrivastava and Li, 2014).”