On Symmetric and Asymmetric LSHs for Inner Product Search

By Behnam Neyshabur, Nati Srebro. 2014

185 citations recorded by the source corpus.

We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, 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 Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “Recommender systems are often based on collaborative ﬁltering which relies on past behavior of users, e.g., past purchases and ratings.”
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).”
TensorCast: forecasting and mining with coupled tensors (2018, methodology): “Approximate methods have also been tried, such as transforming the problem in a near-neighbor search and using locality sensitive hashing (LSH) [26,34].”
Hierarchical Memory Networks (2016, methodology): “There exist several approximate K-MIPS solutions in the literature [8, 9, 7, 10].”
Clustering is Efficient for Approximate Maximum Inner Product Search (2015, methodology): “Later, Neyshabur and Srebro (2015) showed an explicit construction of a symmetric-LSH algorithm for MIPS which had better performance than the previous ALSH algorithms.”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, methodology): “Locality sensitive hashing (Shrivastava and Li, 2014; Neyshabur and Srebro, 2015; Indyk and Motwani, 1998; Andoni et al., 2015) partitions the space using a similarity-preserving hash function.”
Efficient Passage Retrieval with Hashing for Open-domain Question Answering (2021, methodology): “Learning to hash (Wang et al., 2016, 2018) is a method for learning hash functions in a data-dependent manner.”
Learning Binary Codes for Maximum Inner Product Search (2015, background): “Very recently, [24] discussed the power of asymmetric hashes.”
Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time (2023, background): “We start with presenting a pair of transformation ϕ 0 ,ψ 0 : R d → R d +1 such that, given a function g : R d → R , for any x,y in a convex set K , we have Next, we present a standard transformations (Neyshabur & Srebro, 2015) that connects the MaxIP to ANN in unit sphere.”
Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, background): “Note that transformations P andQ are not unique for this task and there are other possibilities [2, 19].”
Deep Cross-Modal Hashing (2016, background): “…research community (Weiss et al., 2008; Raginsky & Lazebnik, 2009; Wang et al., 2010; Liu et al., 2011; Norouzi & Fleet, 2011; Norouzi et al., 2012; Rastegari et al., 2013; Yu et al., 2014; Liu et al., 2014; Shrivastava & Li, 2014; Andoni et al., 2015; Neyshabur & Srebro, 2015; Leng et al., 2015).”