MinHash is an interesting concept that more people should know about, but this article gets one of the details wrong in a confusing way. It claims (twice) that the hash functions applied to each element in the sets being compared should themselves be locality-preserving -- that similar inputs to a hash function should produce similar outputs. But this is not required at all. It is fine and expected for the hash function to return very different answers even when their individual element inputs are very similar (which is good, because such hash functions are easier to design than locality-preserving ones).
The confusion might have occurred because MinHash results in a locality-sensitive hash: if 90% of the elements in the union of A and B are also in their intersection, then on average 90% of the k minimum hash values produced for A will agree with the corresponding ones produced for B. But that's what MinHash builds, not what it takes as input.
have a look at Simhash as well: https://www.matpalm.com/resemblance/simhash/
This is the first time since graduating that I’ve actually had a reason to use set difference :)
MinHash is an interesting concept that more people should know about, but this article gets one of the details wrong in a confusing way. It claims (twice) that the hash functions applied to each element in the sets being compared should themselves be locality-preserving -- that similar inputs to a hash function should produce similar outputs. But this is not required at all. It is fine and expected for the hash function to return very different answers even when their individual element inputs are very similar (which is good, because such hash functions are easier to design than locality-preserving ones).
The confusion might have occurred because MinHash results in a locality-sensitive hash: if 90% of the elements in the union of A and B are also in their intersection, then on average 90% of the k minimum hash values produced for A will agree with the corresponding ones produced for B. But that's what MinHash builds, not what it takes as input.