LSH

Given a set $S \subset U$ of $n$ points, a metric $d$ defined on $U$, and a query point $v$, the nearest neighbor search (NNS) problem finds $v$'s nearest point in $S$:

Potential applications include web search and clustering.

If $U$ is a Euclidean space $\mathcal{R}^d$ for some $d$, the hardness of NNS depends largely on the value of $d$. Suppose $d = 1$, then we can pre-process the points by building a balanced binary search tree on $S$. Finding the nearest point to $v \notin S$ reduces to searching for its predecessor and successor, which takes $O(\log n)$ time. For $d = 2$, we can construct a Voronoi diagram.

For higher dimensions $d$ it is not easy to extend the index structures. A naïve search loops over all points and takes $O(nd)$ time. It is natural to ask whether we can do better. If we are willing to sacrifice accuracy for efficiency, this is possible. Instead of finding the exact nearest neighbor, we relax our goal to finding an approximate nearest neighbor whose distance is within $1 + \epsilon$ of the minimum one.

One possible solution is Johnson–Lindenstrauss decomposition. We can generate a matrix $A \in R^{ O( \frac{ \log n }{ \epsilon^2 } )\times d}$ and multiply it with every element in $S$. The mapping $u \rightarrow Au$ preserves pair-wise distance up to a relative error of $\epsilon$. The pre-processing takes $O( \frac{n d \log n}{\epsilon^2} )$ time. To answer an query, we map $v$ to $Av$, which takes $O(\frac{ d\log n }{ \epsilon^2 } )$ time. Then we perform a loop over all elements of $\{ Au : u \in S\}$, which takes $O(\frac{ n \log n }{ \epsilon^2 } )$ time. Therefore, the total time complexity is $O(\frac{ (n + d) \log n }{ \epsilon^2 } )$.

Hashing

[1] solves the problem by hashing. We call the pair of points that are close to each other the similar pair and the pair that are far from each other the dissimilar pair. Intuitively, we want similar pairs to be hashed to the same bucket and that dissimilar pairs to be hashed to different buckets.

Instead of finding the $(1 + \epsilon)$ approximate nearest neighbor directly, [1] further reduces it to the $(c, r)$-approximate neighbor search (ANNS$(c, r)$) problem, which is defined as follows:

Given a query point $v$, if $\exists s \in S$, then return a point $u$, such that

The reduction from $1 + \epsilon$ to ANNS($c, r$) is not easy. Here we show one that returns the $(1 + \epsilon)^2$ approximate nearest neighbor. Let $d_{\max} = \max_{s, s'} d(s, s')$ and $d_{\min} = \min_{s, s'} d(s, s')$. We build a set of structures that answers ANNS($1 + \epsilon$, r) queries for the values of $r$:

Then given the query point $v$, we do a binary search to find the smallest $r$ that returns a point. This imposes an additional cost of $\ln {\ln \frac{d_{\max} }{d_{\min} } \over \ln (1 + \epsilon) }$.

$(r, cr, p_1, p_2)$-Locality Sensitive Hashing Family

Now we show how to solve the ANNS$(c, r)$ problem with hashing. Designing a perfecting hashing that solves the problem directly is not easy. It is desirable to have some hashing which successes with some probability and then boost its probability systematically. To achieve this, we introduce the idea of $(r, cr, p_1, p_2)$-locality sensitive hashing family.

Given a set of point $V$, a metric $d(\cdot , \cdot)$ defined on $V$, a collection of hash function $\mathcal{H} = \{ h: V \rightarrow Z\}$ is called $(r, cr, p_1, p_2)$ locality sensitive if for any $v, u \in V$ and an $h$ sampled uniformly from $\mathcal{H}$, it holds that

1. If $d(v, u) < r$, then $\Pr_{h \in \mathcal{H} } [h(v) = h(u)] \ge p_1$.
2. If $d(v, u) \ge cr$, then $\Pr_{h \in \mathcal{H} } [h(v) = h(u)] \le p_2$

where $p_2 < p_1 \le 1$. Intuitively, pairs near to each other should be more likely to collide. Hence $p_1 = p_2^{\rho}$ for some $\rho = \log p_1 / \log p_2 < 1$.

Ideally, we have $p_1 \approx 1$ and $p_2 \approx 0$. For other cases we can magnify the gap between $p_1$ and $p_2$ and boost $p_1$ to approximate $1$ and $p_2$ to approximate $0$. The hardness of the boosting highly depends on the value of $c$.

Example

Suppose that $U = \{0, 1\}^d$, $d(u, v) = u \oplus v = |u - v|_1$ and $\mathcal{H} = \{ h_i (u) = u_i \}_{i \in [d]}$, where $h_i$ selects the $i$th bit of $u$. Picking an $h$ uniformly from $\mathcal{H}$ and applying $h$ to $u$ is equivalent to selecting a bit uniformly from $u$. Therefore,

1. If $d(v, u) < r$ ($u$ and $v$ has less then $r$ common bits), then $\Pr_{h \in \mathcal{H} } [h(v) = h(u)] \ge \frac{d - r}{d} = 1 - \frac{r}{d} = p_1$.
2. If $d(v, u) \ge cr$, then $\Pr_{h \in \mathcal{H} } [h(v) = h(u)] \le \frac{d - cr}{d} = 1 - \frac{cr}{d} = p_2$

Now $p_1 \approx \exp(- r / d)$ and $p_2 \approx \exp(- cr / d)$. Hence $\rho \approx \frac{1}{c}$. Indeed it can be proven rigorously that

as $( 1 - \frac{r}{d})^c \ge 1 - \frac{cr}{d}$. There are many ways to prove this. Since we are dealing with probability, we give a probabilistic interpretation of this inequality. Suppose that are $c$ independent events each happening with probability $\frac{r}{d}$. Then the probability that at least one of them happens is given by

On the other hand, by union bound, this is upper bounded by $\frac{cr}{d}$.

Boosting the Probabilities

We would like the boost the probability such that $p_1 \approx 1$ and $p_2 \approx 0$. We follow a two-step approach. First we sample $k$ (to be determined) hash functions independently from $\mathcal{H}$ can concatenate them as a single hash function $g$:

Here $g$ hash a point $v$ to a $k$ dimensional vector. After this, $g(v) = g(u)$ happens only if $h_i(v) = h_i(u)$ for all $i \in [k]$. By independence of $h_i$'s,

1. If $d(v, u) \ge cr$, the collision probability of $u$ with $v$ drops to $p_2^k$:

   $$\Pr [ g(v) = g(u) ] \le p_2^k$$

2. On the other hand, if $d(v, u) < r$, the collision probability also drops to $p_1^k = (p_2^k)^\rho$

   $$\Pr [ g(v) = g(u) ] \ge p_1^k = p_2^{\rho k} = (p_2^{k})^\rho$$

   which is relatively small and not desirable.

We need a second level of boosting to increase the collision probability of similar pairs. Instead of using only one function $g$, we use a collection of independent copies:

where $l$ is the number to be determined. Now,

• If $d(v, u) < r$, the probability that at least one of the $g_i(u)$ equals to $g_i(v)$ is given by$$\begin{aligned} \Pr \left[ \exists i \in [l], \ s.t., \ g_i(u) = g_i(v) \right] &= 1 - (1 - p_1^k)^l \\ &= 1 - (1 - (p_2^k)^\rho)^l \\ &\ge 1 - \exp( - (p_2^k)^\rho l ) \end{aligned}$$

We can take

1. $p_2^k = \frac{1}{n}$, i.e., $k = \frac{\log n }{ \log 1 / p_2 }$.

2. $\exp( - (p_2^k)^\rho l ) = \frac{1}{n}$, i.e., $l = \frac{1}{(p_2^k)^\rho } \ln n = n^\rho \ln n$.

For a fixed query point $q$ and for any fixed $i \in [l]$, by linearity of expectation, the expected number of dissimilar collision is given by

Therefore, there are $l$ of dissimilar collisions over all $i \in [l]$. This implies an expected overhead of $l$ examinations of dissimilar points. However, by Markov inequality, the number of such points is less than $2l$ with probability at least $1 / 2$. The time for examination of dissimilar point is $O(ld) = O(d n^\rho \ln n)$.

Time and Space

Now, given a query point $q$, computing $g_i(q)$ for a fixed $i$ takes $O(k)$ time. Computing $l$ of them takes $O(kl)$ time. In expectation, there are $l$ dissimilar collision points with $q$. Checking one collision point takes $O(d)$ time. Therefore, the expected query time is given by (note that we stop upon finding the first ANN of $q$):

As for the space usage, for each point $u$ in $S$, we need to compute $g_i(u)$ and store this value (we need to store this, because $g_i(u)$ is self could be a large number and when putting $\{ g_i(u) : u \in S\}$ into a hash table, we need to treat $g_i(u)$ as the key and store it for later collision comparison. But is it possible that when there is a collision, we re-compute this value again to avoid storing it ?). We need to repeat this for $l$ hash functions. Therefore, the space usage is given by

Another Boosting Scheme

In last section, we have a scheme that checks $O(n^\rho \ln n)$ dissimilar points in expectation. In this section we achieve it with high probability.

1. First, to reduce the collision probability of dis-similar pairs, we concatenate $k$ functions from $\mathcal{H}$. This gives a$$(r, cr, p_1^k, p_2^k)$$locative sensitive hash function. We determine the value of $k$ later.
2. Second, to boost the collision probability of similar pairs, we use $l$ concatenated hash functions independently. The probability at least one collision occurs is given by$$1 - (1 - p_1^k)^l \ge 1 - e^{-p_1^k \cdot l}$$We require this to happen with constant probability $1 - \frac{1}{e}$, hence we need to set $l = \frac{1}{p_1^k} = (\frac{1}{p_2^k})^\rho$.
3. Now consider a query point $q$. We compute $g_1(q), g_2(q), ..., g_l(q)$ and check the points $u$'s such that $g_i(u) = g_i(q)$ for some $i \in [l]$. Note that we check at most the first $4 n p_2^k l + 1$ points we found. Why $4 n p_2^k l + 1$? In expectation, there are $n p_2^k l$ dissimilar collisions. By Markov inequality, the probability of dissimilar collisions is no more than $4l$ is at most $1 / 4$. By union bound,$$\begin{aligned} &\Pr[\exists \text{ more than } 4l \text{ bad collision } \vee \nexists \text{ good collision }] \\ &\le \frac{1}{e} + \frac{1}{4} \\ &\le \frac{1}{2.5} + \frac{1}{4} \\ &= \frac{5}{16} \end{aligned}$$

Therefore, the boosting strategy successes with constant probability. Now consider the running time of such boosting strategy. When a query point $q$ comes, we need to compute $g_1(q), g_2(q), ..., g_l(q)$, which takes time $kl$. Further, the strategy checks at most $4 n p_2^k l + 1$ points and checking each point takes $O(d)$ time. The overall time used is

To minimize the running time, we need to choose proper value of $k$, such that

It suffice to take $k = \frac{\ln 4nd}{ \ln \frac{1}{p_2} }$. It follows that

and the running time is given by

As $n \succ d$, this is equivalent to

We can repeat the above steps by $\ln n / \ln \frac{16}{5}$ times, to boost the success probability to $1 - \frac{1}{n}$. The overall running time is given by

Reference

1. Indyk, P. and Motwani, R., 1998, May. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (pp. 604-613).