3
$\begingroup$

Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k*(|A|+|B|))$ time to compute.

But isn't it possible to also compute the Jaccard coefficient $\frac {|A \cap B|} {|A \cup B|} $ in $O(|A|+|B|)$ time by simply doing :

1  Given collections A' and B', create hash set datastructures A and B from them.
2. foreach(a in A){ if(a in B)sizeOfIntersection++; }
3. sizeOfUnion = A.size() + B.size() - sizeOfIntersection;
4. Jaccard = sizeOfIntersection / sizeOfUnion;

Assuming [an ammortized] O(1) hash set membership lookup, the complexity of the above is O(|A|+|B|), which is less than with k hash-function minhash.

So how is Minhash more efficient, and what benefit does it provide?

$\endgroup$
2
$\begingroup$

If you only have two sets $A,B$, then you are right: there is no point computing the minhash.

But now suppose you have sets $A_1,A_2,\dots,A_n$, and you want to know whether there exists any pair $A_i,A_j$ with high Jaccard similarity. It's more efficient to compute the minhash of each $A_i$ once, and then use that to help you look for a pair that hash high Jaccard similarity. As a trivial observation, once you've already computed the min-hashes of them all, then estimating the Jaccard similarity of $A_i,A_j$ can be done in $O(k)$ time using the existing minhashes, which can be significantly faster than the naive $O(|A|+|B|)$-time method.

(In fact, once you have the minhashes of all of the sets, there are even cleverer ways to look for pairs $A_i,A_j$ with large similarity.)

This is even mentioned on the Wikipedia page for Minhash: see the section labelled Time analysis. However, you do have to read it pretty carefully to get the point.

$\endgroup$

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.