1
$\begingroup$

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 <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, 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 <r$ 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$ ?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Clement C. Feb 24 '19 at 17:33
  • $\begingroup$ @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 cs.toronto.edu/~anikolov/CSC473W19/Lectures/LSH.pdf $\endgroup$ – Sasho Nikolov Feb 24 '19 at 17:45
  • $\begingroup$ @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!) $\endgroup$ – Clement C. Feb 24 '19 at 17:47
  • 1
    $\begingroup$ @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). $\endgroup$ – Sasho Nikolov Feb 25 '19 at 7:13
  • $\begingroup$ Thanks for the clarification. I'll stop hijacking the question, now. $\endgroup$ – Clement C. Feb 25 '19 at 19:11

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.