In an earlier question of mine asked here : https://math.stackexchange.com/questions/2206095/beginner-level-understanding-concept-on-how-to-derive-probability-of-hash-collis , I got the answer that the number of keys falling into a given bucket. In lay man's term, if I imagine a key to be an image as the data item and its hash as a binary string. The conversion of the image to its binary representation is done via a hash function. I denote 2 images by the variables $x \neq y$ for which I have two binary arrays represting their hash codes as a L-bit string ($L = 20$)

$b_x = [0,1,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0]$ $b_y = [1,1,0,0,0,0,0,1,1,0,0,0,1,1,0,0,1,1,0,0]$

It is known that the the probability that two binary strings are of equal is $Pr(b_x = b_y) = \frac{1}{2^L}$. In the language of hashing this means that the probability that the hash code will collide is $\frac{1}{2^L}$. For $K$ ($K$ is the number of images or data items or keys) values to be equal, the expression becomes ${\frac{1}{2^L} }^K$

I want to know and understand if in Locality Sensitive Hashing we use this expression of probability or not. In the documents https://www.cs.utah.edu/~jeffp/teaching/cs5955/L6-LSH.pdf On page 3 it is explained that the probability of all hashes colliding is

P(all hashes are same) = $s^r$ where $s$ is a similarity measure obtained using a suitable distance metric and the other expressions. I cannot understand why these calculations do not use ${\frac{1}{2^L} }^K$ anywhere. Maybe they do, I am not sure.

Please correct me whereever I am wrong. Thank you.

  • $\begingroup$ That page shows their derivation. What part exactly are you unclear on? What's the first step you don't understand? The idea is also described in many other places, under the name "birthday paradox"; you can read other resources as well. Finally, I don't see any place on that page that mentions the Poisson distribution. $\endgroup$ – D.W. Mar 31 '17 at 22:23
  • $\begingroup$ @D.W.: In another question of mine asked here math.stackexchange.com/questions/2206095/… the solution says that the distribution is Poisson. $\endgroup$ – SKM Apr 1 '17 at 4:08
  • $\begingroup$ You link to a page, then say "they" use a Poisson distribution -- when actually you meant someone else who you didn't mention in the question uses a Poisson distribution. That's confusing. Would you like to edit the question to clarify? And, my question still stands: What part exactly are you unclear on? What's the first step you don't understand? $\endgroup$ – D.W. Apr 1 '17 at 5:49
  • $\begingroup$ @D.W.: I have updated the question, thank you for your feedback. I don't know if the solution posted here is applicable to my question. Shall appreciate your help as well. $\endgroup$ – SKM Apr 1 '17 at 11:01

A hash collision among $K$ values is any two values among those $K$ being equal. The probability of that occurring is the combinatorical expression in the link, from which they estimate the probability (well).

The expression is $\left(1/2^l\right)^{K-1}$ for the probability that all of those values would be equal.

  • $\begingroup$ How is this expression different from locality sensitive hashing en.wikipedia.org/wiki/Locality-sensitive_hashing? I am trying to understand how the probability calculation has been done. If $d(x,y)$ is the similarity function, then the wiki article says that $P(\mathbf{b}_x = \mathbf{b}_y) = d(x,y)$ If $L$ is the number of hash tables, then the probability of finding a point for which a hash has been calculated is $1-{(1-P_1^k)}^L$. I am confused in the probability concepts used in LSH and the probability that I have mentioned in the question. Can you say if these two are same or not? $\endgroup$ – SKM Apr 1 '17 at 4:02
  • $\begingroup$ No where in the wiki link is a mention of the probability of the hash codes being equal, so I don't understand how to use this probability to calculate the probability of finding a point for which a hash has been calculated. I am confused between the two hashing applications / ideas $\endgroup$ – SKM Apr 1 '17 at 4:09
  • 1
    $\begingroup$ Locality-sensitive hashing increases the probability of collisions for some items, so the calculations there aren't applicable. $\endgroup$ – user68806 Apr 1 '17 at 5:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.