Source-linked AI summary
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O'Donnell, Yi Wu, Yuan Zhou
TL;DR
The paper studies how small the rho parameter of an LSH family can be, given its role in approximate near-neighbor search and a gap in known Hamming-space lower bounds. It presents a proof approach for improving those bounds and reports a corresponding lower bound for ℓ_s spaces, while noting that tiny q remains outside the established range.
Problem
The paper asks how small rho can be for a given metric space and c, against a background of Hamming-space lower bounds that assume q is not tiny.
Source: §1 · p. 2, §2.2 · p. 4Method
The paper presents a proof whose essence yields an LSH lower bound when q is not tiny, with detailed calculations deferred.
Source: §3.2 · p. 6Results
For ℓ_s spaces, the stated lower bound is 1/c^s in place of 1/c.
Source: §3 · p. 4Takeaways & Limitations
The Hamming-space lower-bound result also applies when q ≥ 2^-o(d), while the paper identifies tiny q as a more satisfactory unresolved regime.
Source: §2.2 · p. 4The lower-bound arguments assume q is not tiny; the paper describes tiny q as 2^-Θ(d).
Source: §2.2 · p. 4, §4.2 · p. 8
Abstract
from arXiv · showhide
We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in {0,1}^d under the Hamming distance. Recall that here H is said to be an (r, cr, p, q)-sensitive hash family if all pairs x, y in {0,1}^d with dist(x,y) at most r have probability at least p of collision under a randomly chosen h in H, whereas all pairs x, y in {0,1}^d with dist(x,y) at least cr have probability at most q of collision. Typically, one considers d tending to infinity, with c fixed and q bounded away from 0. For its applications to approximate nearest neighbor search in high dimensions, the quality of an LSH family H is governed by how small its "rho parameter" rho = ln(1/p)/ln(1/q) is as a function of the parameter c. The seminal paper of Indyk and Motwani showed that for each c, the extremely simple family H = {x -> x_i : i in d} achieves rho at most 1/c. The only known lower bound, due to Motwani, Naor, and Panigrahy, is that rho must be at least .46/c (minus o_d(1)). In this paper we show an optimal lower bound: rho must be at least 1/c (minus o_d(1)). This lower bound for Hamming space yields a lower bound of 1/c^2 for Euclidean space (or the unit sphere) and 1/c for the Jaccard distance on sets; both of these match known upper bounds. Our proof is simple; the essence is that the noise stability of a boolean function at e^{-t} is a log-convex function of t.
1 Locality Sensitive Hashing
Locality-sensitive hashing (LSH) applies hashing to geometric spaces and is used to solve approximate near-neighbor problems. Its quality is measured by the rho parameter, whose relevance to data-structure complexity assumes q is bounded away from zero.
1 Locality Sensitive Hashing
- LSH hashes points in a metric space so nearby pairs collide with probability at least p and pairs at distance at least cr collide with probability at most q.The family is (r, cr, p, q)-sensitive, with q < p.Source: §1 · p. 2
- The approximate (r, c)-near-neighbor problem asks a data structure to return a point within cr whenever a point within r exists.Several computational-geometry problems reduce to this task.Source: §1 · p. 2
- LSH reduces approximate near-neighbor search to hash-family design, with space O(n^(1+rho)) and query time dominated by O(n^rho log^(1/q)(n)) hash evaluations.The stated reduction is attributed to.Source: §1 · p. 2
- The rho parameter governs LSH quality, and its use in the stated near-neighbor bounds implicitly assumes q is bounded away from zero.The section notes that shrinking rho can matter especially when c is close to 1.Source: §1 · p. 2
2 Previous work
Previous work gives simple LSH upper bounds and establishes Hamming-space lower bounds, with the known lower-bound results restricted to non-tiny q. The Hamming setting is identified as especially powerful for proving lower bounds.
2.1 Upper bounds
- Uniform coordinate projections form a simple LSH family for Hamming space, with collision probabilities 1 − r/d and 1 − cr/d for the near and far distance thresholds.Theorem 2.1 gives its rho upper bound, which is tight only for asymptotically small r/d.Source: §2.1 · p. 3
- For Euclidean space, Andoni and Indyk gave an upper bound roughly 1/c^2, while other practical families were proposed for the Euclidean sphere and ℓ2.For other ℓ_s spaces, Datar, Immorlica, Indyk, and Mirrokni also gave LSH results.Source: §2.1 · p. 3
2.2 Lower bounds
- For fixed c > 1 and 0 < q < 1 as d → ∞, the stated Hamming-space lower bound is a factor of 2 from Indyk and Motwani’s upper bound, with a slightly larger gap when c is close to 1.Source: §2.2 · pp. 3–4
- The prior lower-bound theorem fixes q before d tends to infinity, and the new lower bound is stated to hold for q ≥ 2^-o(d), but tiny q remains an open desired regime.The paper identifies tiny q as q = 2^-Θ(d).Source: §2.2 · p. 4
3 Our result
The paper proves a sharp 1/c − o_d(1) lower bound for the Hamming-space LSH rho parameter and extends lower bounds to other distance settings. Its proof uses log-convexity of hash-family noise stability, with a restriction on how small q may be.
3 Our result
- The lower bound also holds for ℓs, 0 < s < ∞, with 1/c^s replacing 1/c.Source: §3 · p. 4
- The lower bound matches known upper bounds for Euclidean space s = 2 and 0 < s ≤ 1; tightness for 1 < s < 2 is conjectured.Source: §3 · p. 4
- For Jaccard distance on sets, the lower bound matches the known upper bound of Indyk and Motwani.Source: §3 · p. 4
3.1 Noise stability
- The proof relates LSH collision probabilities to noise stability, whose hash-family form is a nonnegative sum of terms weighted by e^-t|S|.The proof uses log-convexity of this stability function to obtain the 1/c lower bound.Source: §3.1 · p. 5, §3.2 · p. 6
3.2 The proof, modulo some tedious calculations
- The proof obtains KH(ct) ≥ q − o(1), but its Chernoff error is exp(−εd), negligible relative to q only when q ≥ 2^{-o(d)}; for q = 2^{-d/B} with large constant B, bound (1) still gives useful information.Source: §3 · p. 4, §3.2 · p. 6
4 Discussion
The discussion clarifies when the LSH-to-near-neighbor reduction supports the usual rho-based bounds and why lower bounds require a restriction on q. It also identifies tiny q as an unresolved boundary for the paper’s lower bound.
4.1 On the reduction from LSH to near neighbor data structures
- A lower bound on q is necessary because a finite metric space admits a trivial LSH family with q = 0 and rho = 0.For each close pair, the construction assigns them the same hash value and all other points distinct values.Source: §4.1 · p. 7
- When q is already at most 1/n, the reduction gives O(n/p) space and O(1/p) time rather than the usual rho-based bounds.The stated rho of 1/3 in the example yields O(n^1.5) space and O(n^0.5) time.Source: §4.1 · p. 7
- The usual reduction powers an LSH family to reduce q to 1/n, but rounding the powering parameter can worsen the resulting bounds.The example with p = 1/n^0.15 and q = 1/n^0.3 has rho = .5, yet rounding k to 4 gives O(n^1.6) space and O(n^0.6) time.Source: §4.1 · p. 7
4.2 On assuming q is not tiny
- The paper’s lower bound assumes q is not tiny; the authors identify q = 2^-d/b for a medium constant such as b = 10 as a range where they lack a compelling lower bound.For n = 2^Θ(d), they state that maintaining the Indyk–Motwani theorem up to n^o(1) factors requires q ≥ 2^-o(d).Source: §4.2 · p. 8
5 Proof details
The proof of Theorem 3.1 uses correlated random strings and bounds on error terms to establish the theorem’s lower bound. It selects a small parameter to control the estimates and checks that the choice satisfies the required assumptions.
Proof of Theorem 3.1
- The proof studies a sensitive hash family on {0,1}^d using two pairs of correlated random strings, with correlations exp(−t/c′) and exp(−t).It sets ǫ = .005∆, t = 2ǫ(1 + ∆/2), and c′ = c(1 + ∆).Source: §5 · p. 8
- The proof bounds e1 and e2 using binomial tail estimates and chooses ∆ to minimize the resulting bound on e.For e1, the proof uses a standard Chernoff bound; estimating e2 similarly requires ǫ to be noticeably smaller than ∆.Source: §5 · pp. 9–10
- The proof chooses ∆ so that the error terms satisfy the bound needed to establish the theorem, then verifies the choice against the assumptions.If ∆ ≤ .005 fails, the proof states that K can be chosen so the claimed lower bound becomes nonpositive.Source: §5 · p. 10