Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
We present the first provably sublinear time hashing algorithm for approximate Maximum Inner Product Search (MIPS). Searching with (un-normalized) inner product as the underlying similarity measure is a known difficult problem and finding hashing schemes for MIPS was considered hard. While the existing Locality Sensitive Hashing (LSH) framework is insufficient for solving MIPS, in this paper we extend the LSH framework to allow asymmetric hashing schemes. Our proposal is based on a key observation that the problem of finding maximum inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search in classical settings. This key observation makes efficient sublinear hashing scheme for MIPS possible. Under the extended asymmetric LSH (ALSH) framework, this paper provides an example of explicit construction of provably fast hashing scheme for MIPS. Our proposed algorithm is simple and easy to implement. The proposed hashing scheme leads to significant computational savings over the two popular conventional LSH schemes: (i) Sign Random Projection (SRP) and (ii) hashing based on p-stable distributions for L 2 norm (L2LSH), in the collaborative filtering task of item recommendations on Netflix and Movielens (10M) datasets.
This paper generalizes the LSH method to account for the (bounded) lengths of the data base vectors, so that the LSH tricks for fast approximate nearest neighbor search can exploit the well-known relation between Euclidian distance and dot product similarity (e.g. as in equation 2) and support MIPS search as well.  They give 3 motivating examples where solving MIPS vs kNN per se is more appropriate and needed.  Their algorithm is essentially equation 9 (using equation 7 compute vector reformulations Q(q) and P(x) of the query a database element respectively). This is based on apparently novel observation (equation 8) that the distance from the query converges to the dot product plus a constant, when a parameter m which exponentiated the P(x) vector elements is sufficiently large (e.g. just 3 is claimed to suffice, leading to vectors Q(q) and P(x) which are just that m times larger than the original input dimensionality.The work seems novel and potentially significant.  One concern though is that the experimental results actually provided do not clearly demonstrate an example where this method is better in practice than brute force linear scan.  The authors claim their "scheme thus offers around  5x speedup over linear scan", at the end of Section 4.2, but they do not clearly state how they implemented linear scan or how much wall clock time linear scan took.  The reason this is a concern is that linear scan can be implemented on modern hardware (multicore CPUs or GPUs) to be ~10x faster using modern libraries (e.g. BLAS SGEMM matrix multiply operatons, using batches of queries and the fully batch of database vectors) than the vector based, one-query-at-a-time loops that presumably the proposed hased-baed scheme requires, due to the cache-awareness of tile-based SGEMM ops for modern hardware.  Furthermore, hashing schemes will have additional overheads that must be demonstrated to not add significance constants -- especially when the speedup versus simple, low-constant-overhead linear scan approaches are relatively low (such as 5x here).  In short, this paper's focus on the 5x less dot products being performed for 90% accuracy does not prove that the method actually is, or will be for practical problems in general, faster in a practical wall clock sense than well-implemented linear scans.