Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
This solves the hard problem of efficient similarity search with inner products, which is crucial for applications like recommendation systems, and it introduces a novel theoretical framework.
The authors tackled the problem of Maximum Inner Product Search (MIPS) by developing the first provably sublinear time algorithm using asymmetric Locality Sensitive Hashing (ALSH), which enables efficient hashing for un-normalized inner products, and they evaluated it on Netflix and Movielens datasets for item recommendations.
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.