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

Maximum inner-product search ranks candidate vectors by their unnormalized dot product with a query. This similarity creates difficulties for conventional locality-sensitive hashing. The talk introduces an asymmetric hashing framework in which queries and stored vectors undergo different transformations, turning approximate MIPS into a standard approximate nearest-neighbor problem. An explicit construction provides provably sublinear search and a simple implementation. Experiments on recommendation tasks using Netflix and MovieLens data compare the method with sign random projection and p-stable hashing for Euclidean distance, demonstrating substantial computational savings.