LSH Probabilistic guarantees

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

• 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. Feb 24 '19 at 17:33
• @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 – Sasho Nikolov Feb 24 '19 at 17:45
• @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. Feb 24 '19 at 17:47
• @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 Feb 25 '19 at 7:13
• Thanks for the clarification. I'll stop hijacking the question, now. – Clement C. Feb 25 '19 at 19:11