Lower bounds on Locality Sensitive Hashing

Rajeev Motwani  Assaf Naor  Rina Panigrahy

Abstract

Given a metric space (X, d_{X}), c ≥ 1, r > 0, and p, q ∈ [0, 1], a distribution over mappings ℋ : X → is called a (r, cr, p, q)-sensitive hash family if any two points in X at distance at most r are mapped by ℋ to the same value with probability at least p, and any two points at distance greater than cr are mapped by ℋ to the same value with probability at most q. This notion was introduced by Indyk and Motwani in 1998 as the basis for an efficient approximate nearest neighbor search algorithm, and has since been used extensively for this purpose. The performance of these algorithms is governed by the parameter ρ = \frac{log(1/p)}{log(1/q)}, and constructing hash families with small ρ automatically yields improved nearest neighbor algorithms. Here we show that for X = ℓ_{1} it is impossible to achieve ρ ≤ \frac{1}{2c}. This almost matches the construction of Indyk and Motwani which achieves ρ ≤ \frac{1}{c}.

1 Introduction

In this note we study the complexity of finding the nearest neighbor of a query point in certain high dimensional spaces using Locality Sensitive Hashing (LSH). The nearest neighbor problem is formulated as follows: Given a database of n points in a metric space, preprocess it so that given a new query point it is possible to quickly find the point closest to it in the data set. This fundamental problem arises in numerous applications, including data mining, information retrieval, and image search, where distinctive features of the objects are represented as points in ^{d}. There is a vast amount of literature on this topic, and we shall not attempt to discuss it here. We refer the interested reader to the papers [6, 5, 4, 7], and especially to the references therein, for background on the nearest neighbor problem.

While the exact nearest neighbor problem seems to suffer from the “curse of dimensionality”, many efficient techniques have been devised for finding an approximate solution whose distance from the query point is at most c times its distance from the nearest neighbor. One of the most versatile and efficient methods for approximate nearest neighbor search is based on Locality Sensitive Hashing, as introduced by Indyk and Motwani in 1998 [6]. This method has been refined and improved in several papers- the most recent algorithm can be found in [4]. We also refer the reader to the LSH website, where more information on this algorithm can be found, including its implementation and code- all this can be found

at http://web.mit.edu/andoni/www/LSH/index.html. The LSH approach to the approximate nearest

neighbor problem is based on the following concept.

Definition 1.1. Let (X, d_{X}) be a metric space, r, R > 0 and p, q ∈ [0, 1]. A distribution over mappings ℋ : X → is called a (r, R, p, q)-sensitive hash family if for any x, y ∈ X,

• d_{X}(x, y) ≤ r ⟹ Pr[ℋ (x) = ℋ (y)] ≥ p .

• d_{X}(x, y) > R ⟹ Pr[ℋ (x) = ℋ (y)] ≤ q .

Given c ≥ 1 we define

ρ_{X}(c) = sup_{r>0}inf \{ \frac{log(1/p)}{log(1/q)} : ∃(r, cr, p, q) − sensitive hash family ℋ : X → \} .  (1)

Of particular interest is the case X = ℓ_{s}^{d}, for some s ≥ 1 and d ∈ . In this case we define

ρ_{s}(c) = lim sup_{d→∞}ρ_{ℓ_{s}^{d}}(c) .

The importance of these parameters stems from the following application to approximate nearest neighbor search. It will be convenient to discuss it in the framework of the following decision version of the c-approximate nearest neighbor problem: Given a query point, find any element of the data set which is at distance at most cr from it, provided that there is a data point at distance at most r from the query point. This decision version is known as the (r, cr)-near neighbor problem. It is well known that the reduction to the decision version adds only a logarithmic factor in the time and space complexity [6, 5]. The following theorem was proved in [6]; the exact formulation presented here is taken from [4].

Theorem 1.2. Let (X, d_{X}) be a metric on a subset of ^{d}. Suppose that (X, d_{X}) admits a (r, cr, p, q)-sensitive hash family ℋ , and write ρ = \frac{log(1/p)}{log(1/q)}. Then for any n ≥ \frac{1}{q} there exists a randomized algorithm for (r, c) near neighbor on n-point subsets of X which uses O (dn + n^{1+ρ})space, with query time dominated by O (n^{ρ}) distance computations and O (n^{ρ} log_{1/q}n)evaluations of hash functions from ℋ .

Thus, obtaining bounds on ρ_{X}(c) is of great algorithmic interest. It is proved in [6] that ρ_{1}(c) ≤ 1/c, and for small values of c, namely c ∈ [1, 10], is was shown in [4] that this inequality is strict. We refer to [4] for numerical data on the best know estimates for ρ_{1}(c) for small c. For s = 2 a recent result of Andoni and Indyk [1] shows that ρ_{2}(c) ≤ 1/c^{2}, and for general s ∈ [1, 2] the best known bounds [4] are ρ_{s}(c) ≤ max{1/c, 1/c^{s}}.

The main purpose of this note is to obtain lower bounds on ρ_{1}(c) and ρ_{2}(c) which nearly match the bounds obtained from the constructions in [6, 4, 1]. Our main result is:

Theorem 1.3. For every c, s ≥ 1,

ρ_{s}(c) ≥ \frac{e^{\frac{1}{c^{s}}} − 1}{e^{\frac{1}{c^{s}}} + 1} ≥ \frac{e − 1}{e + 1} · \frac{1}{c^{s}} ≥ \frac{0.462}{c^{s}} .  (2)

The second to last inequality in (2) follows from concavity of the function t ↦ \frac{e^{t}−1}{e^{t}+1} on [0, ∞). Observe also that as c → ∞, \frac{e^{1/c}−1}{e^{1/c}+1} ∼ \frac{1}{2c}. It would be very interesting to determine lim sup_{c→∞} c · ρ_{1}(c) exactly- due to Theorem 1.3 and the results of [6] we currently know that this number is in the interval [1/2, 1].

2 Proof of Theorem 1.3

The basic idea in the proof of Theorem 1.3 is simple. We consider the random subset A of the cube {0, 1}^{d} consisting of points u for which ℋ (u) = ℋ (0). The second condition in Definition 1.1 forces A to be small in expectation. But, when A is small we can bound from above the probability that after r steps, the random walk starting at a random point in A will end up in A. We obtain this upper bound using a Fourier analytic argument, and in combination with the first condition in Definition 1.1 we deduce the desired bound on ρ_{1}(c).

Theorem 1.3 follows from the following result:

Proposition 2.1. Let ℋ be a (r, R, p, q)-sensitive hash family on the Hamming cube ({0, 1}^{d}, ∥ · ∥_{1}). Assume that r is an odd integer and that R < \frac{d}{2}. Then

p ≤ (q + e^{− \frac{1}{d}(\frac{d}{2}−R)^{2}})^{\frac{e^{2r/d}−1}{e^{2r/d}+1}} .

Choosing R ≈ \frac{d}{2} − \sqrt{d logd}and r ≈ R/c in Proposition 2.1, and letting d → ∞, yields Theorem 1.3 in the case s = 1. The case of general s ≥ 1 follows from the fact that for x, y ∈ {0, 1}^{d}, ∥x − y∥_{s} = ∥x − y∥_{1}^{1/s}.

The proof of Proposition 2.1 will be broken into a few lemmas.

Lemma 2.2. Let ℋ be a (r, R, p, q)-sensitive hash family on the Hamming cube ({0, 1}^{d}, ∥ · ∥_{1}). Consider the random subset S ⊆ {0, 1}^{d} given by A = {u ∈ {0, 1}^{d} : ℋ (u) = ℋ (0)}. Then

|A| ≤ ∑_{k=0}^{⌊R⌋}\binom{d}{k} + q · ∑_{k=⌊R⌋+1}^{d}\binom{d}{k} .

Proof. We simply write

|A| = ∑_{u∈{0,1}^{d}}Pr[ℋ (u) = ℋ (0)]
≤ |{u ∈ {0, 1}^{d} : ∥u∥_{1} ≤ R}| + q · |{u ∈ {0, 1}^{d} : ∥u∥_{1} > R}|
= ∑_{k=0}^{⌊R⌋}\binom{d}{k} + q · ∑_{k=⌊R⌋+1}^{d}\binom{d}{k} .

Corollary 2.3. Assume that R < \frac{d}{2}. Then, using the notation of Lemma 2.2, we have that

|A| ≤ 2^{d}(q + e^{− \frac{1}{d}(\frac{d}{2}−R)^{2}}) .

Proof. This follows from Lemma 2.2 and the standard estimate ∑ _{k≤ \frac{d}{2}−a} \binom{d}{k} ≤ 2^{d} · e^{− \frac{a^{2}}{d}} .

Lemma 2.4 (Random walk lemma). Let r be an odd integer. Given ∅ B ⊆ {0, 1}^{d}, consider the random variable Q_{B} ∈ {0, 1}^{d} defined as follows: Choose a point x ∈ B uniformly at random, and perform r-steps of the standard random walk on the Hamming cube starting from x. The point thus obtained will be denoted Q_{B}. Then

Pr[Q_{B} ∈ B] ≤ (\frac{|B|}{2^{d}})^{\frac{e^{2r/d}−1}{e^{2r/d}+1}} .

Proof. We begin by recalling some background and notation on Fourier analysis on the Hamming cube. Given S ⊆ {1, …d}, the Walsh function W_{S} : {0, 1}^{d} → {−1, 1} is defined by

W_{S}(u) = (−1)^{∑ _{j∈S} u_{j}} .

For f : {0, 1}^{d} → we set

f̂(S) = \frac{1}{2^{d}} ∑_{u∈\{0,1\}^{d}}f (u)W_{S}(u) ,

so that f can be decomposed as follows:

f = ∑_{S⊆{1,...,d}}f̂(S)W_{S} .

For every f, g : {0, 1}^{d} → we write

⟨f, g⟩ = \frac{1}{2^{d}} ∑_{u∈\{0,1\}^{d}}f (u)g(u) .

By Parseval’s identity,

⟨f, g⟩ = ∑_{S⊆{1,...,d}}f̂(S)ĝ(S) .

For ε ∈ [0, 1] the Bonami-Beckner operator T_{ε} is defined as

T_{ε}f = ∑_{S⊆{1,...,d}}ε^{|S|}f̂(S)W_{S} .

The Bonami-Beckner inequality [3, 2] states that for every f : {0, 1}^{d} → ,

∑_{S⊆\{1,...,d\}}ε^{2|S|}f̂(S)^{2} = ∥T_{ε}f ∥_{2}^{2} = \frac{1}{2^{d}} ∑_{u∈\{0,1\}^{d}}(T_{ε}f (u))^{2} ≤ ∥f ∥_{1+ε^{2}}^{2} = (\frac{1}{2^{d}} ∑_{u∈\{0,1\}^{d}}f (u)^{1+ε^{2}} )^{\frac{2}{1+ε^{2}}} .

Specializing to the indicator of B ⊆ {0, 1}^{d} we get that

∑_{S⊆\{1,...,d\}}ε^{2|S|} ˆ1_{B}(S)^{2} ≤ (\frac{|B|}{2^{d}})^{\frac{2}{1+ε^{2}}} .  (3)

Now, let P be the transition matrix of the standard random walk on {0, 1}^{d}, i.e. P_{uv} = 1/d if u and v differ in exactly one coordinate, P_{uv} = 0 otherwise. By a direct computation we have that for every S ⊆ {1, …, d},

PW_{S} = (1 − \frac{2|S|}{d}) W_{S} ,

i.e. W_{S} is an eigenvector of P with eigenvalue 1 − \frac{2|S|}{d}. The probability that the random walk starting form a random point in B ends up in B after r steps equals

Pr[Q_{B} ∈ B] = \frac{1}{|B|} ∑_{a,b∈B}(P^{r})_{ab}

= \frac{2^{d}}{|B|}⟨P^{r}1_{B}, 1_{B}⟩
= \frac{2^{d}}{|B|} ∑_{S⊆\{1,...,d\}} ˆ1_{B}(S)^{2} (1 − \frac{2|S|}{d})^{r}

≤ \frac{2^{d}}{|B|} ∑_{\begin{matrix}S⊆\{1,...,d\} \\ |S|≤d/2 \end{matrix}} ˆ1_{A}(S)^{2} (1 − \frac{2|S|}{d})^{r} ,

where we used the fact that r is odd (i.e. we dropped negative terms).

Thus, using (3) we see that

Pr[Q_{B} ∈ B] ≤ \frac{2^{d}}{|B|} ∑_{S⊆\{1,...,d\}} ˆ1_{B}(S)^{2} · e^{−2r|S|/c} ≤ \frac{2^{d}}{|B|}· (\frac{|B|}{2^{d}})^{\frac{2}{1+e^{−2r/c}}} = (\frac{|B|}{2^{d}})^{\frac{1−e^{−2r/c}}{1+e^{−2r/c}}} .

Proof of Proposition 2.1. Let A be as in Lemma 2.2. Assume that r is an odd integer and R < \frac{d}{2}. Since the Hamming distance from Q_{A}to A is at most r, we know that Pr[Q_{A} ∈ A] = Pr[ℋ (Q_{A}) = ℋ (0)] ≥ p. On the other hand by Lemma 2.4, Corollary 2.3, and Jensen’s inequality,

p ≤ Pr[Q_{A} ∈ A] ≤ [(\frac{|A|}{2^{d}})^{\frac{e^{2r/d}−1}{e^{2r/d}+1}} ]≤ (\frac{|A|}{2^{d}})^{\frac{e^{2r/d}−1}{e^{2r/d}+1}} ≤ (q + e^{− \frac{1}{d}(\frac{d}{2}−R)^{2}})^{\frac{e^{2r/d}−1}{e^{2r/d}+1}} .

References

[1] A. Andoni and P. Indyk. Faster algorithms for high dimensional nearest neighbor problems. Manuscript, 2005.

[2] W. Beckner. Inequalities in Fourier analysis. Ann. of Math. (2), 102(1):159–182, 1975.

[3] A. Bonami. Étude des coefficients de Fourier des fonctions de L^{p}(G). Ann. Inst. Fourier (Grenoble), 20(fasc. 2):335–402 (1971), 1970.

[4] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on pstable distributions. In SoCG ’04: Proceedings of the Twentieth Annual Symposium on Computational Geometry, pages 253–262, New York, NY, USA, 2004. ACM Press.

[5] S. Har-Peled. A replacement for Voronoi diagrams of near linear size. In 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), pages 94–103. IEEE Computer Soc., Los Alamitos, CA, 2001.

[6] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC ’98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 604–613, New York, NY, USA, 1998. ACM Press.

[7] R. Panigrahy. Entropy based nearest neighbor search in high dimensions. In SODA ’06: Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete Algorithms. To appear.