<p>A family <span class="math-container">$H$</span> is <span class="math-container">$(r,cr,p_1,p_2)$</span>-sensitive if for all <span class="math-container">$x,y \in \mathbb{R}^d$</span> we have:</p>

<ul>
<li><p><span class="math-container">$\lVert x-y\rVert &lt;r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$</span>, and </p></li>
<li><p><span class="math-container">$\lVert x-y\rVert &gt; cr \quad \Rightarrow\quad \Pr[h(x)=h(y)] \leq p_2 $</span></p></li>
</ul>

<p>We can amplify  the gap between <span class="math-container">$p_1,p_2$</span> by using concatenation:
<span class="math-container">$g(x) = h_1(x)h_2(x)\cdots h_k(x)$</span>
and <span class="math-container">$L$</span> tabels, so we have <span class="math-container">$g_1,\dots,g_L$</span></p>

<p>For each <span class="math-container">$\delta &gt; 0$</span> we can choose <span class="math-container">$k,L$</span> s.t. for a query point <span class="math-container">$q$</span>, if
<span class="math-container">$\lVert x-q\rVert &lt;r$</span> then <span class="math-container">$\Pr[\exists i \: \: s.t. \: g_i(x)=g_i(q)]&gt;1-\delta$</span> </p>

<p>My question is: what guarantees do I have for the "bad" points?
Given a query point <span class="math-container">$q$</span>, what is the ratio between good points (i.e., <span class="math-container">$r$</span>-close or <span class="math-container">$cr$</span>-close points) and the bad points (far points) in the bucket <span class="math-container">$g_i(q)$</span>. Can I bound it for some (carefully chosen) <span class="math-container">$k,L$</span> ?</p>

CC BY-SA 4.0
2019-02-24T17:33:43.330Z
Are you sure you want to use concatenation this way ("$x\equiv y$ iff at least one of the hashes coincides"), where it seems that you'll have to pay for a union bound, instead of saying "$x\equiv y$ iff at least a $\frac{p_1+p_2}{2}$ fraction of the hashes coincide"? (threshold/majority vote)
Clement C.
CC BY-SA 4.0
2019-02-24T17:45:06.867Z
@ClementC. The usual strategy is indeed to use concatenation so that the $p_1$ vs $p_2$ gap becomes $p_1^k$ vs $p_2^k$. The expected number of far points that collide with a given $q$ is bounded by $Lnp_2^k$. I have some lecture notes http://www.cs.toronto.edu/~anikolov/CSC473W19/Lectures/LSH.pdf
Sasho Nikolov
CC BY-SA 4.0
2019-02-24T17:47:34.770Z
@SashoNikolov Interesting. I won't ask too many details here not to "pollute" this question, but is there a brief argument why this concatenation is better than the majority vote? (also, what you wrote with $p_i^k$ seems to hint at an AND rule  "collision when they *all* agree", while the OP uses an OR " collision when *at least one* agrees"), doesn't it?) (Edit: thanks for the link!)
Clement C.
CC BY-SA 4.0
2019-02-25T07:13:11.667Z
@ClementC. It's an "OR of AND" tree kind of thing.  You concatenate $k$ hash values to form a new hash function with a $p_1^k/p_2^k$ gap. But then you do this $L$ times and build $L$ different hash tables. So the query point $q$ collides with a close point $p$ if there is at least one hash table in which $q$ and $p$ collide (this is the OR), and to collide in the hash table, all $k$ hash values must be the same (this is the AND).
Sasho Nikolov
CC BY-SA 4.0
2019-02-25T19:11:47.187Z
Thanks for the clarification. I'll stop hijacking the question, now.
Clement C.
<computational-geometry><hash-function><high-dimensional-geometry>
LSH Probabilistic guarantees
John B
# LSH Probabilistic guarantees

(Asked by: username_0 on 2019-02-24)

A family $H$ is $(r,cr,p\_1,p\_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:

* $\lVert x-y\rVert , and
* $\lVert x-y\rVert > cr \quad \Rightarrow\quad \Pr[h(x)=h(y)] \leq p\_2 $

We can amplify the gap between $p\_1,p\_2$ by using concatenation:
$g(x) = h\_1(x)h\_2(x)\cdots h\_k(x)$
and $L$ tabels, so we have $g\_1,\dots,g\_L$

For each $\delta > 0$ we can choose $k,L$ s.t. for a query point $q$, if
$\lVert x-q\rVert  then $\Pr[\exists i \: \: s.t. \: g\_i(x)=g\_i(q)]>1-\delta$

My question is: what guarantees do I have for the "bad" points?
Given a query point $q$, what is the ratio between good points (i.e., $r$-close or $cr$-close points) and the bad points (far points) in the bucket $g\_i(q)$. Can I bound it for some (carefully chosen) $k,L$ ?

**Tags:** computational-geometry, hash-function, high-dimensional-geometry
> **Comments:**
> **username_1**: Are you sure you want to use concatenation this way ("$x\equiv y$ iff at least one of the hashes coincides"), where it seems that you'll have to pay for a union bound, instead of saying "$x\equiv y$ iff at least a $\frac{p_1+p_2}{2}$ fraction of the hashes coincide"? (threshold/majority vote)  
> **username_2**: @ClementC. The usual strategy is indeed to use concatenation so that the $p_1$ vs $p_2$ gap becomes $p_1^k$ vs $p_2^k$. The expected number of far points that collide with a given $q$ is bounded by $Lnp_2^k$. I have some lecture notes http://www.cs.toronto.edu/~anikolov/CSC473W19/Lectures/LSH.pdf  
> **username_1**: @SashoNikolov Interesting. I won't ask too many details here not to "pollute" this question, but is there a brief argument why this concatenation is better than the majority vote? (also, what you wrote with $p_i^k$ seems to hint at an AND rule  "collision when they *all* agree", while the OP uses an OR " collision when *at least one* agrees"), doesn't it?) (Edit: thanks for the link!)  
> **username_2**: @ClementC. It's an "OR of AND" tree kind of thing.  You concatenate $k$ hash values to form a new hash function with a $p_1^k/p_2^k$ gap. But then you do this $L$ times and build $L$ different hash tables. So the query point $q$ collides with a close point $p$ if there is at least one hash table in which $q$ and $p$ collide (this is the OR), and to collide in the hash table, all $k$ hash values must be the same (this is the AND).  
> **username_1**: Thanks for the clarification. I'll stop hijacking the question, now.  

---

## 0 answers

