Similarity join (Min-hash)

Brilliant stuff. Isn&#x27;t the XORing essentially just equivalent to a 1-time pad -- which isn&#x27;t very hash-like. I&#x27;d think using a PRNG [1] with the initial hash value as the seed, to generate more values, would be more effective.<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Pseudorandom_number_generator" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Pseudorandom_number_generator</a>

&gt; The probability of C also having true in the row would be equal to Jaccard’s similarity!<p>That&#x27;s clear, call this P1<p>&gt; The probability that two documents A and B having the same representative token is, equal again to Jaccard’s similarity<p>That&#x27;s less clear (call this P2) and not equivalent to the first statement, afaict. In fact, this probability seems lower than the previous one. Consider the table:<p><pre><code> token A B a False True b True True </code></pre> This counts as matching under P1, but not under P2.<p>What am I missing here?<p>In order words, the number of cases where `reptoken(A) = reptoken(B)` is a subset of cases where `reptoken(A) is in B`

I understand the theory here, and it seems like it works, but it sure would have been nice seeing some actual examples from a corpus of docs.