Source-linked AI summary
On Symmetric and Asymmetric LSHs for Inner Product Search
Behnam Neyshabur, Nathan Srebro
TL;DR
The paper asks when symmetric or asymmetric LSH is possible for inner-product search. It analyzes constrained vector spaces and shows that symmetry suffices for normalized-query MIPS, while asymmetry is necessary in a bounded but unnormalized setting and impossible over all of R^d.
Problem
The paper studies whether asymmetric hashing provides an advantage over symmetric hashing for inner-product similarity under different constraints on queries and data vectors.
Method
The paper characterizes symmetric and asymmetric LSH feasibility across vector spaces and compares SIMPLE-LSH with prior asymmetric schemes for MIPS.
Results
A universal symmetric LSH exists for normalized queries and bounded database vectors, while bounded unnormalized queries require an asymmetric LSH and all of R^d admits neither type.
Takeaways & Limitations
Asymmetry is unnecessary for the standard normalized-query MIPS setting but genuinely useful when queries and data are bounded without query normalization.
Takeaways & Limitations
The prior L2-ALSH(SL) scheme is not universal and requires parameters tuned to the threshold and approximation ratio.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper revisits whether asymmetry is necessary for inner-product LSH, showing that a symmetric scheme works in the normalized-query, bounded-data MIPS setting while asymmetry is needed in another bounded setting.
- Motivation: Maximum Inner Product Search (MIPS) asks for the database vector with maximum inner product with a query.MIPS appears in recommendation, multi-class prediction, structural SVM, and vision applications.
- Prior work: Shrivastava and Li argued that no symmetric LSH exists for inner-product similarity and proposed an asymmetric LSH using distinct query and database mappings.Their nonexistence result concerns all of R^d, whereas their asymmetric construction assumes normalized queries and bounded data vectors.
- Contributions: Over all of R^d, neither symmetric nor asymmetric LSH exists; with normalized queries and bounded data, a universal symmetric LSH is possible.The paper therefore finds no advantage to hash asymmetry in the MIPS setting considered.
- Contributions: When both queries and data are bounded but queries are unnormalized, symmetric LSH is impossible while asymmetric LSH exists.This setting demonstrates a case where asymmetry is genuinely useful.
- Contributions: Under normalized queries and bounded database vectors, SIMPLE-LSH is symmetric, parameter-free, and has stronger theoretical guarantees and better empirical performance than L2-ALSH(SL).The paper studies the transformation underlying SIMPLE-LSH as an LSH scheme and compares it with L2-ALSH(SL).
2. Locality Sensitive Hashing
The paper defines symmetric and asymmetric locality-sensitive hashing over possibly different constrained spaces, then identifies the collision-probability gap required for approximate search.
- LSH framework: The LSH definition requires high collision probability for pairs with similarity at least S and low collision probability for pairs with similarity at most cS.The definition permits different constraints on the two compared spaces X and Y.
- LSH framework: For approximate search, the required parameters satisfy p1 > p2 and c < 1, with hashing quality ρ determined by the logarithmic ratio of collision probabilities.The resulting data structure uses time O(n^ρ log n) and space O(n^1+ρ).
- Symmetry and asymmetry: A symmetric hash applies one random function h to both spaces, whereas an asymmetric hash uses separate mappings f and g, often formed from deterministic transformations P and Q followed by one random map.The two mappings target a common hash alphabet while allowing different preprocessing of query and database objects.
- Universality: A universal LSH or ALSH must satisfy the required collision guarantees for every threshold S > 0 and approximation ratio 0 < c < 1.The paper also distinguishes constrained pairs of spaces from a single common space.
3. No ALSH over Rd
The paper proves that inner-product locality-sensitive hashing is impossible even with asymmetric mappings when both spaces are the entire R^d.
- Impossibility result: For every d ≥ 2, S > 0, and 0 < c < 1, no asymmetric (S, cS)-ALSH exists for inner-product similarity over R^d.This strengthens the earlier symmetric nonexistence result by ruling out asymmetry as well.
- Proof strategy: The proof reduces the d-dimensional claim to a two-dimensional subspace and assumes an ALSH with collision gap p1 > p2.It then constructs sequences of points whose inner products encode a triangular sign matrix.
- Contradiction: The triangular matrix has margin complexity Ω(log N), whereas any collision-probability matrix has max-norm at most 1 and its shifted version has max-norm at most 2.These bounds force the collision gap to shrink as the matrix dimension grows.
4. Maximum Inner Product Search
The paper compares asymmetric and symmetric LSHs for MIPS under normalized-query and bounded-database assumptions. It introduces SIMPLE-LSH, proves universal guarantees, and evaluates its hashing quality and recommendation performance against prior methods.
- Problem setting: Queries can be normalized and database vectors bounded inside the unit sphere without changing the MIPS argmax.This restricts attention to the constrained query and database spaces used for the hash analysis.
- SIMPLE-LSH: SIMPLE-LSH is a parameter-free, universal, symmetric LSH over normalized queries and bounded database vectors.The construction uses a spherical random projection into the binary alphabet {±1}.
- L2-ALSH(SL): L2-ALSH(SL) uses parameterized mappings and can achieve an (S, cS)-ALSH guarantee for suitable parameter choices.Its mappings are parameterized by m, U, and r, with the parameters selected for each threshold and approximation ratio.
- L2-ALSH(SL): L2-ALSH(SL) is not universal because no fixed parameter choice works across all thresholds and approximation ratios.This is problematic because the relevant MIPS threshold can vary with the query.
- Theoretical comparison: SIMPLE-LSH dominates L2-ALSH(SL) and SIGN-ALSH(SL) in the theoretical comparison of optimal hashing quality ρ.The comparison evaluates tuned parameter choices for the asymmetric methods against SIMPLE-LSH's fixed construction.
- Empirical evaluation: On Netflix and Movielens, SIMPLE-LSH shows a dramatic empirical improvement over L2-ALSH(SL), while SIGN-ALSH(SL) performs almost the same as SIMPLE-LSH.SIMPLE-LSH is simpler and parameter-free, whereas SIGN-ALSH(SL) requires tuning two parameters.
5. Unnormalized Queries
With bounded but unnormalized queries and database vectors, no symmetric LSH is possible, and the previously proposed L2-ALSH(SL) and SIGN-ALSH(SL) also fail. The paper instead introduces SIMPLE-ALSH, a parameter-free universal asymmetric LSH for this setting.
- Setting and impossibility: No symmetric LSH exists when queries and database vectors are both bounded but unnormalized.
- Setting and impossibility: L2-ALSH(SL) is not an (S, cS)-ALSH for bounded vectors whenever S < (c + 1)/2.This includes all S < 1/2 because c < 1.
- SIMPLE-ALSH: SIMPLE-ALSH uses paired transformations that preserve inner products while mapping both sides to unit-norm vectors.The construction defines separate query and database mappings before applying the same random hash.
- SIMPLE-ALSH: SIMPLE-ALSH is a universal ALSH over bounded vectors for every 0 < S and c < 1.
6. Conclusion
The paper characterizes when symmetric and asymmetric LSHs are possible for inner product similarity across three vector-space settings. Asymmetry is unnecessary with normalized queries, but necessary when both sides are bounded and unnormalized.
- Over R^d, neither symmetric nor asymmetric LSH is possible for inner product similarity.
- With normalized queries and bounded database vectors, a universal symmetric LSH is possible.
- With bounded but unnormalized queries and database vectors, symmetric LSH is impossible but universal asymmetric LSH is possible.
- SIMPLE-LSH is symmetric, parameter-free, and universal, while the earlier asymmetric hashes are not valid in the setting where asymmetry is required.
- Using a symmetric hash still requires normalizing queries without normalizing database vectors, so the problem formulation remains asymmetric.
A. Another variant
The appendix examines SIGN-ALSH(SL), a modified asymmetric hash using the mappings of L2-ALSH(SL) with the random projection hash used by SIMPLE-LSH. It proves that SIGN-ALSH(SL) lacks the desired ALSH guarantees in both normalized-query and fully bounded settings.
- Construction: SIGN-ALSH(SL) combines L2-ALSH(SL)'s two mappings with SIMPLE-LSH's random projection hash.
- Conclusion: The appendix concludes that the theoretical failures established for L2-ALSH(SL) also apply to SIGN-ALSH(SL).
- Unnormalized setting: For any S > 0 and 0 < c < 1, SIGN-ALSH(SL) is not an (S, cS)-ALSH when both vectors are merely bounded.
- Normalized-query setting: SIGN-ALSH(SL) is not an (S, cS)-ALSH over bounded database vectors and normalized queries.
- Normalized-query setting: For any U, m, and r, SIGN-ALSH(SL) is not a universal ALSH over bounded database vectors and normalized queries.
MAX-NORM
The max-norm argument bounds every collision-probability matrix generated by hashes. This provides the matrix-norm constraint used in the paper's impossibility analysis.
- For finite object sets and hashes, the collision-probability matrix records P(i, j) = P[f(x_i) = g(y_j)].
- Every collision-probability matrix has max-norm at most 1.
- The bound follows because each deterministic biclustering matrix has max-norm at most 1, and expectation preserves the bound by convexity and Jensen's inequality.
- The all-ones matrix has a rank-one factorization, providing a simple reference factorization for the max-norm analysis.
MARGIN COMPLEXITY
This section introduces margin complexity for sign matrices by stating its definition.
- Margin complexity is defined for any sign matrix Z.