Similarity join (Min-hash)
blog.yellowflash.in
Similarity join (Min-hash)
1–10 of 10 posts
Re: Similarity join (Min-hash)
#2Brilliant stuff. Isn't the XORing essentially just equivalent to a 1-time pad -- which isn't very hash-like. I'd think using a PRNG [1] with the initial hash value as the seed, to generate more values, would be more effective.
Re: Similarity join (Min-hash)
#3Brilliant stuff. Isn't the XORing essentially just equivalent to a 1-time pad -- which isn't very hash-like. I'd think using a PRNG [1] with the initial hash value as the seed, to generate more values, would be more effective. https://en.wikipedia.org/wiki/Pseudorandom_number_generator
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.
Re: Similarity join (Min-hash)
#4Brilliant stuff. Isn't the XORing essentially just equivalent to a 1-time pad -- which isn't very hash-like. I'd think using a PRNG [1] with the initial hash value as the seed, to generate more values, would be more effective. https://en.wikipedia.org/wiki/Pseudorandom_number_generator
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 tha…
Can't edit the post. I meant to say "the same two hash values."
Re: Similarity join (Min-hash)
#5I 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.
Re: Similarity join (Min-hash)
#6> The probability of C also having true in the row would be equal to Jaccard’s similarity!
That's clear, call this P1
> The probability that two documents A and B having the same representative token is, equal again to Jaccard’s similarity
That'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:
token A B
a False True
b True True
What am I missing here?
In order words, the number of cases where `reptoken(A) = reptoken(B)` is a subset of cases where `reptoken(A) is in B`
Re: Similarity join (Min-hash)
#7> The probability of C also having true in the row would be equal to Jaccard’s similarity! That's clear, call this P1 > The probability that two documents A and B having the same representative token is, equal again to Jaccard’s similarity That'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: token A B a Fal…
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.
Re: Similarity join (Min-hash)
#8Brilliant stuff. Isn't the XORing essentially just equivalent to a 1-time pad -- which isn't very hash-like. I'd think using a PRNG [1] with the initial hash value as the seed, to generate more values, would be more effective. https://en.wikipedia.org/wiki/Pseudorandom_number_generator
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.
Re: Similarity join (Min-hash)
#9> The probability of C also having true in the row would be equal to Jaccard’s similarity! That's clear, call this P1 > The probability that two documents A and B having the same representative token is, equal again to Jaccard’s similarity That'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: token A B a Fal…
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.
Maybe I'm missing something, but I don't think that addresses my concerns around P1 and P2 being different.
Re: Similarity join (Min-hash)
#10> The probability of C also having true in the row would be equal to Jaccard’s similarity! That's clear, call this P1 > The probability that two documents A and B having the same representative token is, equal again to Jaccard’s similarity That'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: token A B a Fal…
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.