Similarity join (Min-hash) (opens in new tab)

Yeah, I had a similar intuition about that approach possibly being weak or problematic. However, if my cursory reading of the algorithm is at all correct, the goal may simply be to consistently choose another hash value (a different min hash) and it may work fine. In other words, the same hash values would be considered the minimum after XORing with a random number and they will be different from the initial hash that was selected as the minimum without XORing. Those are the behaviors that matter and not so much that the hashes that result from the XORing are cryptographically secure.

MinHash is a CPU hog due to precisely this step -- cheap rehashes are the order of the day.

I don't think xor works, but simple arithmetic, IIRC h_i(key) = i*h(key) + C mod 2^32, is viable and SIMD-friendly. Look up minwise-independent hash functions.

The probability of the `b` being chosen for A is 1 (No other choice) and for B it is 1/2. The probability of `b` being chosen for both (The only common token), is |{(b,b)}| / |{(a, a), {(a, b)}| = 1/2 which is jaccard's similarity |{b}|/|{a, b}|

I could have explained that a bit better I suppose.

The net result of the hashing etc. is to shuffle the unique elements of A union B. In that shuffled union, the first element is in at least one of A or B; if it's in both it's in the intersection. The chance of that is J.