title: How many hash functions are required in a minhash algorithm
body: <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>