22 min
Seminar, Hosted by Neural Information Processing Systems (NIPS 2014)
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
Recording
Abstract
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.
Topics
- Maximum inner-product search, search World Wide
- unnormalized dot product, search World Wide
- asymmetric hashing, search World Wide
- locality-sensitive hashing
- sublinear search, search World Wide
- sign random projection, search World Wide
- p-stable hashing, search World Wide
- recommendation tasks, search World Wide
- MovieLens, search World Wide