<p>LSH functions are useful for approximate nearest neighbor search. 
They are usually defined, for distance metric <span class="math-container">$d$</span> and <span class="math-container">$c&gt;1$</span> as follows:</p>

<blockquote>
  <p>A family of hash functions is <span class="math-container">$(r, cr, p_1, p_2)$</span>-LSH with <span class="math-container">$p_1 \ge p_2$</span> and <span class="math-container">$c &gt; 1$</span> if:</p>
</blockquote>

<ul>
<li><span class="math-container">$\Pr[h(x) = h(y)] \ge p_1$</span> when <span class="math-container">$d(x, y) \le r$</span> (close points).</li>
<li><span class="math-container">$\Pr[h(x) = h(y)] \le p_2$</span> when <span class="math-container">$d(x, y) \ge cr$</span> (distant points).</li>
</ul>

<p>The family is interesting when <span class="math-container">$p_1&gt;p_2$</span> and they are often compared using <span class="math-container">$\rho = \frac{\log 1/p_1}{\log 1/p_2}$</span> which directly affect the space and query time.</p>

<p>I am wondering what is known for mapping of balls using LSH functions. 
Let's say that a ball <span class="math-container">$B_R(x)$</span> is mapped entirely if <span class="math-container">$h(x)=h(y)$</span> <strong>for any</strong> <span class="math-container">$y$</span> such that <span class="math-container">$d(x, y) \le R$</span>. </p>

<p>Intuitively, if <span class="math-container">$R_1\ll r$</span>, we may be able to expect that <span class="math-container">$B_{R_1}(x)$</span> will be mapped entirely with a reasonable probability.</p>

<hr>

<blockquote>
  <p><strong>Question 1: Given <span class="math-container">$r, R_1, c, x$</span>, how can we derive a lower bound on the probability that <span class="math-container">$B_{R_1}(x)$</span> is mapped entirely for known LSH families?</strong></p>
</blockquote>

<hr>

<p>The other side is that if <span class="math-container">$cr\ll  R_2$</span>, we may be able to expect that with decent probability <strong>no point</strong> <span class="math-container">$y$</span> for which <span class="math-container">$d(x,y)\ge R_2$</span> will have <span class="math-container">$h(x)=h(y)$</span>.</p>

<blockquote>
  <p><strong>Question 2: Given <span class="math-container">$r, R_2, c, x$</span>, can we derive a lower bound on the probability that <em>no</em> <span class="math-container">$y$</span> for which <span class="math-container">$d(x,y)\ge R_2$</span> has <span class="math-container">$h(x)=h(y)$</span>?</strong></p>
</blockquote>

CC BY-SA 4.0
2019-05-23T21:16:48.007Z
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? https://ilyaraz.org/static/class/scribes/scribe19.pdf
Sasho Nikolov
CC BY-SA 4.0
2019-05-23T21:25:03.423Z
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?
R B
CC BY-SA 4.0
2019-05-23T21:38:47.973Z
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$.
Sasho Nikolov
<ds.algorithms><pr.probability><computational-geometry>
Mapping of entire balls using Locality Sensitive Hashing (LSH)
R B
# Mapping of entire balls using Locality Sensitive Hashing (LSH)

(Asked by: username_0 on 2019-05-23)

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)$?**

**Tags:** ds.algorithms, pr.probability, computational-geometry
> **Comments:**
> **username_1**: 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? https://ilyaraz.org/static/class/scribes/scribe19.pdf  
> **username_0**: 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?  
> **username_1**: 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$.  

---

## 0 answers

