Optimal lower bounds for locality sensitive hashing (except when q is tiny)

Locality Sensitive Hashing

Locality Sensitive Hashing (LSH) is a widely-used algorithmic tool which brings the classic technique of hashing to geometric settings. It was introduced for general metric spaces in the seminal work of Indyk and Motwani [IM98]. Indyk and Motwani showed that the important problem of (approximate) nearest neighbor search can be reduced to the problem of devising good LSH families. Subsequently, numerous papers demonstrating the practical utility of solving high-dimensional nearest neighbor search problems via the LSH approach [GIM99, Buh01, CDF+01, SVD03, RPH05, DDGR07]. For a survey on LSH, see Andoni and Indyk [AI08].

We recall the basic definition from [IM98]:

As mentioned, the most useful application of LSH is to the approximate near neighbor problem in high dimensions:

Several important problems in computational geometry reduce to the approximate near neighbor problem, including approximate versions of nearest neighbor, furthest neighbor, close pair, minimum spanning tree, and facility location. For a short survey of these topics, see Indyk [Ind04].

Regarding the reduction from $(r,c)$-near neighbor problem to LSH, it is usual (see [Ind01, DIIM04]) to credit roughly the following theorem to [IM98, GIM99]:

The rho parameter of an $(r,cr,p,q)$-sensitive LSH family ${\cal H}$ is

Please note that in Theorem 1.1, it is implicitly assumed [Ind09] that $q$ is bounded away from . For “subconstant” values of $q$, the theorem does not hold. This point is discussed further in Section 4.

Because of Theorem 1.1, there has been significant interest [DIIM04, TT07, AI08, Ney10] in determining the smallest possible $\rho$ that can be obtained for a given metric space and value of $c$. Constant factors are important here, especially for the most natural regime of $c$ close to $1$. For example, shrinking $\rho$ by an additive $.5$ leads to time and space savings of $\Theta(\sqrt{n})$.

Previous work

The original work of Indyk and Motwani [IM98] contains the following simple yet strong result:

There is an LSH family ${\cal H}$ for $\{0,1\}^{d}$ under the Hamming distance which for each $c>1$ has rho parameter

In this theorem, the family is simply the uniform distribution over the $d$ functions $h_{i}(x)=x_{i}$. For a given $c$ and $r$, this family is obviously $(r,cr,1-r/d,1-cr/d)$-sensitive, whence

(The complexity of evaluating a hash function $\bm{h}\sim{\cal H}_{t}$ also increases as $t$ increases.)

2 Lower bounds

There is one known result on lower bounds for LSH, due to Motwani, Naor, and Panigrahy [MNP07]:

Fix $c>1$, $0<q<1$, and consider $d\to\infty$. Then there exists some $r=r(d)$ such that for any LSH family ${\cal H}$ for $\{0,1\}^{d}$ under Hamming distance which is $(r,cr,p,q)$-sensitive must satisfy

The metric setting of $\{0,1\}^{d}$ under Hamming distance is the most powerful setting for lower bounds; as Motwani, Naor, and Panigrahy note, one can immediately deduce a lower bound of

As $c\to\infty$, the lower bound in Theorem 2.4 approaches $\frac{1}{2c}$. This is a factor of $2$ away from the upper bound of Indyk and Motwani. The gap is slightly larger in the more natural regime of $c$ close to $1$; here one only has that $\rho({\cal H})\geq\frac{e-1}{e+1}\frac{1}{c}\approx\frac{.46}{c}$.

Note that in Theorem 2.4, the parameter $q$ is fixed before one lets $d$ tend to $\infty$; i.e., $q$ is assumed to be at least a “constant”. Even though this is the same assumption implicitly made in the application of LSH to near-neighbors (Theorem 1.1), we feel it is not completely satisfactory. In fact, as stated in [MNP07], Theorem 2.4 still holds so long as $q\geq 2^{-o(d)}$. Our new lower bound for LSH also holds for this range of $q$. But we believe the most satisfactory lower bound would hold even for “tiny” $q$, meaning $q=2^{-\Theta(d)}$. This point is discussed further in Section 4.

Our result

In this work, we improve on Theorem 2.4 by obtaining a sharp lower bound of $\frac{1}{c}-o_{d}(1)$ for every $c>1$. This dependence on $c$ is optimal, by the upper bound of Indyk and Motwani. The precise statement of our result is as follows:

Here, the precise meaning of the $\widetilde{O}(\cdot)$ expression is

where $K$ is a universal constant, and we assume $d/\ln(2/q)\geq 2$, say.

As mentioned, the lower bound is only of the form $\frac{1}{c}-o_{d}(1)$ under the assumption that $q\geq 2^{-o(d)}$. For $q$ of the form $2^{-d/B}$ for a large constant $B$, the bound (1) still gives some useful information.

As with the Motwani–Naor–Panigrahy result, because our lower bound is for $\{0,1\}^{d}$ we may immediately conclude:

This lower bound matches the known upper bounds for Euclidean space $s=2$ ([AI08]) and $0<s\leq 1$ ([DIIM04]). It seems reasonable to conjecture that it is also tight at least for $1<s<2$.

Finally, the lower bound in Theorem 3.1 also holds for the Jaccard distance on sets, matching the upper bound of Indyk and Motwani [IM98]. We explain why this is true in Section 3.2, although we omit the very minor necessary changes to the proof details.

Our proof of Theorem 3.1 requires some facts about boolean noise stability. We begin by recalling some basics of the analysis of boolean functions.

For $0<\rho\leq 1$, we say that $(\bm{x},\bm{y})$ are $\rho$-correlated random strings in $\{0,1\}^{d}$ if $\bm{x}$ is chosen uniformly at random and $\bm{y}$ is formed by rerandomizing each coordinate of $\bm{x}$ independently with probability $1-\rho$.

where $\langle w,z\rangle=\sum_{i\in U}w_{i}z_{i}$ is the usual inner product.In the case that $U$ is countably infinite, we require our functions $f$ to have $\|f(x)\|_{2}<\infty$ for all $x\in\{0,1\}^{d}$.

We also extend the notion of noise stability to hash families:

If ${\cal H}$ is a hash family on $\{0,1\}^{d}$, we define

By combining this definition with equation (2) and Proposition 3.3, we immediately deduce:

Let ${\cal H}$ be a hash family on $\{0,1\}^{d}$. Then

Finally, it is sometimes more natural to express the parameter $\rho$ as $\rho=e^{-t}$, where $t\in[0,\infty)$. (For example, we can think of a $\rho$-correlated pair $(\bm{x},\bm{y})$ by taking $\bm{x}$ to be uniformly random and $\bm{y}$ to be the string that results from running the standard continuous-time Markov Chain on $\{0,1\}^{d}$, starting from $\bm{x}$, for time $td$.) We make the following definition:

2 The proof, modulo some tedious calculations

We now present the essence of our proof of Theorem 3.1. It will be quite simple to see how it gives a lower bound of the form $\frac{1}{c}-o_{d}(1)$ (assuming $q$ is not tiny). Some very tedious calculations (Chernoff bounds, elementary inequalities, etc.) are needed to get the precise statement given in Theorem 3.1; the formal proof is therefore deferred to Section 5.

Let ${\cal H}$ be a hash family on $\{0,1\}^{d}$, and let us consider

We then deduce the desired lower bound of $1/c$ from the following theorem and its corollary:

For any hash family ${\cal H}$ on $\{0,1\}^{d}$, $t\geq 0$, and $c\geq 1$,

As mentioned, we give the careful proof keeping track of approximations in Section 5. But first, we note what we view as a shortcoming of the proof: after deducing $K_{{\cal H}}(ct)\geq q-o_{d}(1)$, we wish to “neglect” the additive $o_{d}(1)$ term. This requires that $o_{d}(1)$ indeed be negligible compared to $q$! Being more careful, the $o_{d}(1)$ arises from a Chernoff bound applied to a Binomial$(d,ct)$ random variable, where $t>0$ is very small. So to be more precise, the error term is of the form $\exp(-\epsilon d)$, and hence is only negligible if $q\geq 2^{-o(d)}$.

Discussion

As described in Section 1, it is normally stated that the quality of an $(r,cr,p,q)$-sensitive LSH family ${\cal H}$ is governed by $\rho=\ln(1/p)/\ln(1/q)$, and more specifically that ${\cal H}$ can be used to solve the $(r,c)$-near neighbor problem with roughly $O(n^{1+\rho})$ space and query time $O(n^{\rho})$. However, this involves the implicit assumption that $q$ is bounded away from .

Given an $(r,cr,p,q)$-sensitive family ${\cal H}$ of functions $X\to U$ and a positive integer $k$, we define the family ${\cal H}^{\otimes k}$ by drawing $\bm{h}_{1},\dots,\bm{h}_{k}$ independently from ${\cal H}$ and forming the function $\bm{h}:X\to U^{k}$, $\bm{h}(x)=(\bm{h}_{1}(x),\dots,\bm{h}_{k}(x))$. It is easy to check that ${\cal H}^{\otimes k}$ is $(r,cr,p^{k},q^{k})$-sensitive.

Indyk and Motwani show that if one has an $(r,cr,p^{\prime},q^{\prime})$-sensitive hash family with $q^{\prime}\leq 1/n$, then one can obtain a $(r,c)$-near neighbor data structure with space roughly $O(n/p^{\prime})$ and query time roughly $O(1/p^{\prime})$. Thus given an arbitrary $(r,cr,p,q)$-sensitive family ${\cal H}$, Indyk and Motwani suggest using the Powering Construction with $k=\log_{1/q}(n)$. The resulting ${\cal H}^{\otimes k}$ is $(r,cr,p^{\prime},1/n)$-sensitive, with $p^{\prime}=p^{k}=n^{-\rho}$, yielding an $O(n^{1+\rho})$ space, $O(n^{\rho})$ time data structure.

However this argument makes sense only if $k$ is a positive integer. For example, with the trivially “optimal” LSH family, we have $q=0$ and thus $k=-\infty$. Indeed, whenever $q\leq 1/n$ to begin with, one doesn’t get $O(n^{1+\rho})$ space and $O(n^{\rho})$ time, one simply gets $O(n/p)$ space and $O(1/p)$ time. For example, a hypothetical LSH family with $p=1/n^{.5}$ and $q=1/n^{1.5}$ has $\rho=1/3$ but only yields an $O(n^{1.5})$ space, $O(n^{.5})$ time near neighbor data structure.

The assumption $q>1/n$ is still not enough for the deduction in Theorem 1.1 to hold precisely. The reason is that the Indyk–Motwani choice of $k$ may not be an integer. For example, suppose we design an $(r,cr,p,q)$-sensitive family ${\cal H}$ with $p=1/n^{.15}$ and $q=1/n^{.3}$. Then $\rho=.5$. However, we cannot actually get an $O(n^{1.5})$ space, $O(n^{.5})$ time data structure from this ${\cal H}$. The reason is that to get $q^{k}\leq 1/n$, we need to take $k=4$. Then $p^{k}=1/n^{.6}$, so we only get an $O(n^{1.6})$ space, $O(n^{.6})$ time data structure.

The effect of rounding $k$ up to the nearest integer is not completely eliminated unless one makes the assumption, implicit in Theorem 1.1, that $q\geq\Omega(1)$. Under the weaker assumption that $q\geq n^{-o(1)}$, the conclusion of Theorem 1.1 remains true up to $n^{o(1)}$ factors. To be completely precise, one should assume $q\geq 1/n$ and take $k=\lceil\log_{1/q}(n)\rceil$. If we then use $k\leq\log_{1/q}(n)+1$, the Powering Construction will yield an LSH family with $q^{\prime}\leq 1/n$ and $p^{\prime}=(n/q)^{-\rho}$. In this way, one obtains a refinement of Theorem 1.1 with no additional assumptions:

2 On assuming q𝑞q is not tiny

Let us return from the near-neighbor problem to the study of locality sensitive hashing itself. Because of the “trivial” LSH family, it is essential to impose some kind of lower bound on how small the parameter $q$ is allowed to be. Motwani, Naor, and Panigrahy carry out their lower bound for LSH families on $\{0,1\}^{d}$ under the assumption that $q\geq\Omega(1)$, but also note that it goes through assuming $q\geq 2^{-o(d)}$. Our main result, Theorem 3.1, is also best when $q\geq 2^{-o(d)}$, and is only nontrivial assuming $q\geq 2^{-d/B}$ for a sufficiently large constant $B$.

One may ask what the “correct” lower bound assumed on $q$ should be. For the Indyk–Motwani application to $(r,c)$-near neighbor data structures, the answer seems obvious: “$1/n$”. Indeed, since the Indyk–Motwani reduction immediately uses Powering to reduce the $q$ parameter down to $1/n$, the most meaningful LSH lower bounds would simply involve fixing $q=1/n$ and trying to lower bound $p$.

There is an obvious catch here, though, which is that in the definition of LSH, there is no notion of “$n$”! Still, in settings such as $\{0,1\}^{d}$ which have a notion of dimension, $d$, it seems reasonable to think that applications will have $n=2^{\Theta(d)}$. In this case, to maintain the Indyk–Motwani Theorem 4.1 up to $n^{o(1)}$ factors one would require $q\geq 2^{-o(d)}$. This is precisely the assumption that this paper and the Motwani–Naor–Panigrahy paper have made. Still, we believe that the most compelling kind of LSH lower bound for $\{0,1\}^{d}$ would be nontrivial even for $q=2^{-d/b}$ with a “medium” constant $b$, say $b=10$. We currently do not have such a lower bound.

Proof details

We require the following lemma, whose proof follows easily from Proposition 3.4 and the definition of hash family sensitivity:

Let ${\cal H}$ be an $(r,cr,p,q)$-sensitive hash family on $\{0,1\}^{d}$ and suppose $(\bm{x},\bm{y})$ is a pair of $e^{-u}$-correlated random strings. Then

We now prove Theorem 3.1, which for convenience we slightly rephrase as follows:

Let $0<\Delta=\Delta(c,d,q)<.005$ be a small quantity to be chosen later, and let $\epsilon=.005\Delta$. Suppose that ${\cal H}$ is an $((\epsilon/c)d,\epsilon d,p,q)$-sensitive hash family for $\{0,1\}^{d}$. Our goal is to lower bound $\rho=\ln(1/p)/\ln(1/q)$. By the Powering Construction we may assume that $q\leq 1/e$, and hence will use $\ln(1/q)\geq 1$ without further comment. Define also $t=2\epsilon(1+\Delta/2)$ and $c^{\prime}=c(1+\Delta)$.

Let $(\bm{x}_{1},\bm{y}_{1})$ be $\exp(-t/c^{\prime})$-correlated random strings and let $(\bm{x}_{2},\bm{y}_{2})$ be $\exp(-t)$-correlated random strings. Using the two bounds in Lemma 5.1 separately, we have

We will also ensure that the quantity in (7) is positive by making the following

Substituting the three estimates (5)–(7) into (4) we obtain

We now estimate $e_{1}$ and $e_{2}$ in terms of $\Delta$ (and $\epsilon$), after which we will choose $\Delta$ so as to minimize $e$. By definition, $e_{1}$ is the probability that a Binomial$(d,\eta_{1})$ random variable exceeds $(\epsilon/c)d$, where $\eta_{1}=(1-\exp(t/c^{\prime}))/2$. Let us select $\delta_{1}$ so that $(1+\delta_{1})\eta_{1}=\epsilon/c$. Thus

Here we used the definitions of $t$ and $c^{\prime}$, and then the assumption $\Delta<.005$. Using a standard Chernoff bound, we conclude

using the fact that $\delta^{2}/(2+\delta)$ is increasing in $\delta$, and $\Delta<.005$ again. We additionally estimate

Here the second inequality used $t/2c^{\prime}\leq.01$, which certainly holds since $t/2c^{\prime}\leq\epsilon=.005\Delta$. The third inequality used $\Delta\leq.005$. Substituting this into (11) we obtain our upper bound for $e_{1}$,

Our estimation of $e_{2}$ is quite similar:

where $\eta_{2}=(1-\exp(-t))/2$ and $\delta_{2}$ is chosen so that $(1-\delta_{2})\eta_{2}=\epsilon$. This entails

This expression is the reason we were forced to take $\epsilon$ noticeably smaller than $\Delta$. Using our specific setting $\epsilon=.005\Delta$, we conclude

where we used $\Delta\leq.005$ again. As for $\eta_{2}$, we can lower bound it similarly to $\eta_{1}$, obtaining

Substituting our lower bounds for $\delta_{2}$ and $\eta_{2}$ into (13) yields

Plugging our upper bounds (12), (14) for $e_{1}$, $e_{2}$ into (10) gives

where $K_{1}$ is an absolute constant. For $K_{1}$ sufficiently large, this makes all three terms in the bound (15) at most

It only remains to check whether this is a valid choice for $\Delta$. First, we note that with this choice, assumptions (8) and (9) follow from (12) and (14) (and increasing $K_{1}$ if necessary). Second, we required that $\Delta\leq.005$. This may not hold. However, if it fails then we have

We can then trivialize the theorem by taking $K=(K_{1}/.005)^{3}$, making the claimed lower bound for $\rho$ smaller than $1/c-1/c^{1/3}\leq 0$. ∎

Acknowledgments

The authors would like to thank Alexandr Andoni, Piotr Indyk, Assaf Naor, and Kunal Talwar for helpful discussions.

References