On Symmetric and Asymmetric LSHs for Inner Product Search
This addresses a theoretical and practical gap in similarity search methods for machine learning and data retrieval, though it appears incremental as it refines existing LSH approaches.
The paper tackles the problem of designing locality sensitive hashes (LSH) for inner product similarity, showing that a simple symmetric LSH exists with stronger guarantees and better empirical performance than a previously proposed asymmetric LSH, while also identifying a variant where asymmetry is needed.
We consider the problem of designing locality sensitive hashes (LSH) for inner product similarity, and of the power of asymmetric hashes in this context. Shrivastava and Li argue that there is no symmetric LSH for the problem and propose an asymmetric LSH based on different mappings for query and database points. However, we show there does exist a simple symmetric LSH that enjoys stronger guarantees and better empirical performance than the asymmetric LSH they suggest. We also show a variant of the settings where asymmetry is in-fact needed, but there a different asymmetric LSH is required.