Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)

By Anshumali Shrivastava, Ping Li. 2014

108 citations recorded by the source corpus.

Recently it was shown that the problem of Maximum Inner Product Search (MIPS) is efficient and it admits provably sub-linear hashing algorithms. Asymmetric transformations before hashing were the key in solving MIPS which was otherwise hard. In the prior work, the authors use asymmetric transformations which convert the problem of approximate MIPS into the problem of approximate near neighbor search which can be efficiently solved using hashing. In this work, we provide a different transformation which converts the problem of approximate MIPS into the problem of approximate cosine similarity search which can be efficiently solved using signed random projections. Theoretical analysis show that the new scheme is significantly better than the original scheme for MIPS. Experimental evaluations strongly support the theoretical findings.

Subfields: Aerospace Engineering, Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Algorithms & Complexity

How researchers see this paper

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

In Aerospace Engineering

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Algorithms & Complexity

Citations in the corpus

Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, background): “Recently, it was shown that general inner products for real vectors can be efficiently solved by using asymmetric locality sensitive hashing schemes [35, 37].”
Phrase-Indexed Question Answering: A New Challenge for Scalable Document Comprehension (2018, methodology): “are retrieved in modern search engines via similarity search algorithms (Shrivastava and Li, 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].”
On Symmetric and Asymmetric LSHs for Inner Product Search (2014, methodology): “(8) Shrivastava and Li (2014a) establish2 that for any 0 < c < 1 and 0 < S < 1, there exists 0 < U < 1, r > 0, m ≥ 1, such that l2-alsh(sl) is an (S, cS)-ALSH over X•,Y◦.”
Hierarchical Memory Networks (2016, methodology): “ractical applications, it is often sufﬁcient to have an approximate result for K-MIPS, trading speed-up at the cost of the accuracy. There exist several approximate K-MIPS solutions in the literature [8, 9, 7, 10]. All the approximate K-MIPS solutions add a form of hierarchical structure to the memo”
Contextual Memory Trees (2018, methodology): “Classical approaches are inadequate: a) Exact nearest neighbor algorithms (including memory systems that use them (Kaiser et al., 2017)) are computationally inefﬁcient except in special cases (Dasgupta & Sinha, 2015; Beygelzimer et al., 2006) and do not learn. b) Approximate Nearest Neigh-bors via L”
Clustering is Efficient for Approximate Maximum Inner Product Search (2015, methodology): “The mappings are deﬁned as follows: As shown in Shrivastava and Li (2015), mapping P brings all the vectors to roughly the same norm: we have , with the last term vanishing as m → + ∞ , since || x i || 2 ≤ U 1 .”