<p><strong>Just use 1 hash function!</strong> (and save the <code>1/(f ε^2)</code> smallest values.) </p>

<p>Check out <a href="https://arxiv.org/pdf/1303.5479v2.pdf" rel="nofollow noreferrer">this article</a> for the state of the art practical and theoretical bounds. It has this nice graph (below), explaining why you probably want to use just one 2-independent hash function and save the <code>k</code> smallest values.</p>

<p>When estimating set sizes the paper shows that you can get a relative error of approximately <code>ε = 1/sqrt(f k)</code> where <code>f</code> is the jaccard similarity and <code>k</code> is the number of values kept. So if you want error <code>ε</code>, you need <code>k=1/(fε^2)</code> or if your sets have similarity around <code>1/3</code> and you want a <code>10%</code> relative error, you should keep the <code>300</code> smallest values.</p>

<p><a href="https://i.stack.imgur.com/lHc9c.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/lHc9c.png" alt="graph"></a></p>
How many hash functions are required in a minhash algorithm
<p>I am keen to try and implement minhashing to find near duplicate content. <a href="http://blog.cluster-text.com/tag/minhash/">http://blog.cluster-text.com/tag/minhash/</a> has a nice write up, but there the question of just how many hashing algorithms you need to run across the shingles in a document to get reasonable results.</p>

<p>The blog post above mentioned something like 200 hashing algorithms. <a href="http://blogs.msdn.com/b/spt/archive/2008/06/10/set-similarity-and-min-hash.aspx">http://blogs.msdn.com/b/spt/archive/2008/06/10/set-similarity-and-min-hash.aspx</a> lists 100 as a default.</p>

<p>Obviously there is an increase in the accuracy as the number of hashes increases, but how many hash functions is reasonable?</p>

<p>To quote from the blog</p>

<blockquote>
  <p>It is tough to get the error bar on our similarity estimate much
  smaller than [7%] because of the way error bars on statistically
  sampled values scale — to cut the error bar in half we would need four
  times as many samples.</p>
</blockquote>

<p>Does this mean that mean that decreasing the number of hashes to something like 12 (200 / 4 / 4) would result in an error rate of 28% (7 * 2 * 2)?</p>