LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows:

A family of hash functions is $(r, cr, p_1, p_2)$-LSH with $p_1 \ge p_2$ and $c > 1$ if:

  • $\Pr[h(x) = h(y)] \ge p_1$ when $d(x, y) \le r$ (close points).
  • $\Pr[h(x) = h(y)] \le p_2$ when $d(x, y) \ge cr$ (distant points).

The family is interesting when $p_1>p_2$ and they are often compared using $\rho = \frac{\log 1/p_1}{\log 1/p_2}$ which directly affect the space and query time.

I am wondering what is known for mapping of balls using LSH functions. Let's say that a ball $B_R(x)$ is mapped entirely if $h(x)=h(y)$ for any $y$ such that $d(x, y) \le R$.

Intuitively, if $R_1\ll r$, we may be able to expect that $B_{R_1}(x)$ will be mapped entirely with a reasonable probability.

Question 1: Given $r, R_1, c, x$, how can we derive a lower bound on the probability that $B_{R_1}(x)$ is mapped entirely for known LSH families?

The other side is that if $cr\ll R_2$, we may be able to expect that with decent probability no point $y$ for which $d(x,y)\ge R_2$ will have $h(x)=h(y)$.

Question 2: Given $r, R_2, c, x$, can we derive a lower bound on the probability that no $y$ for which $d(x,y)\ge R_2$ has $h(x)=h(y)$?

  • $\begingroup$ To make sure I understand the definitions, isn't the object you are asking for (assuming you want both properties to be satisfied simultaneously) equivalent to a padded decomposition? ilyaraz.org/static/class/scribes/scribe19.pdf $\endgroup$ – Sasho Nikolov May 23 '19 at 21:16
  • $\begingroup$ I'm not sure I follow. Which assumptions? I'm asking if for current LSH families we can answer Q1 or Q2 (any of them by itself is fine). It seems that in the link you sent the number of points is finite? $\endgroup$ – R B May 23 '19 at 21:25
  • $\begingroup$ I see, I did miss that. I was saying that a hash function that has the two properties you are asking about is a padded decomposition. Padded decompositions do exist for infinite metrics too, for example a randomly shifted grid in the plane for Euclidean norm. I haven't seen anyone analyze such things for typical LSH families though. Also, as most LSH families involve some random projection, you will probably not be able to guarantee the property in Question 2 for any finite $R_2$. $\endgroup$ – Sasho Nikolov May 23 '19 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.