# Why use minhash instead of directly computing Jaccard coefficient?

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?

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.