Number of minhash_bits for 1% relative error for 0.1% similarity. about hyperminhash

[yunwilliamyu]

Ah, what's going on is that while the number of minhash bits is correct, the number of minhash buckets is not. I think that's actually a bug in the final space bound in the paper. The standard minhash bound of error on the order 1/sqrt(k) is actually an absolute error. So if you're using 2^16 buckets, then the minhash error for the Jaccard index (not even using hyperminhash compression) is going to be on the order of 1/256 ~ 0.004 asymptotically. The analysis in the paper focuses on the number of additional collisions from using hyperminhash compression, but the number of buckets still determines an absolute error in Jaccard index estimation.

Thanks for catching that.

[kportertx]

If I understand correctly, 16 index_bits should provide 0.4% absolute error when estimating the Jaccard index, correct?

[kportertx]

BTW, I believe you meant to use union_filled_buckets on line 257.

[yunwilliamyu]

Mostly yes. The 16 index_bits for standard MinHash gives a 0.004 standard deviation on the Jaccard index so long as there are no MinHash collisions. (i.e. so with 95% probability, it'll be within 0.8% absolute error, as that's 2 standard deviations).

The analysis in my paper was mostly bounding the additional error that comes from doing a floating point compression on the hash values. So you also need sufficient minhash_bits in order to prevent the floating point compression from adding to the error.

Does that make sense?

Also, thanks for the catch! Yes, I did.

[kportertx]

Yes, thank you. I was able to explain my remaining mysteries with the absolute vs relative error confusion. Thanks again for providing a reference implementation, it has been been very helpful to compare against.