yunwilliamyu

Things like b-bit MinHash [Li, Konig, 2010]. A good summary of the problem with asymptotics and some lower bounds is Pagh, Stockel, Woodruff, 2014, "Is Min-Wise Hashing Optimal for Summarizing Set Intersection." There's been more recent work, but that's a good place to start.

These other techniques have lower space complexity than MinHash (or even HyperMinHash) but have the con that they lose the streaming and composability properties of MinHash. One of the main advantages of a MinHash (or HLL) sketch is that you can combine sketch(A) with sketch(B) to get sketch(A v B). Alternately, the data structures can be progressively updated as you see a stream of items. The other fingerprinting techniques often require storing auxiliary data during the generation process.

Should note here that my benchmarks are comparing HyperMinHash to MinHash. I didn't directly compare to HyperLogLog in the paper, though there exist other papers (mostly in the CS theory literature) that do compare MinHash to HyperLogLog in various intersection regimes.

Hi there! I'm the lead author on the paper that Seif (expertly) implements. You're right that my Python implementation isn't at all optimized, as I was more interested in the theory, though I think Seif's Go implementation does much better.

HyperLogLogs are normally used for intersections through inclusion-exclusion (though there are more sophisticated methods out there). As such, it is really good when the two sets A and B being intersected are about the same size and the intersection is large. It performs poorly when |A ^ B| << |A v B| because inclusion-exclusion means that a small error in the union size results in a large relative error in the intersection size.

HyperLogLog uses 6 bits per bucket in normal use. For our purposes, the rule of thumb we propose uses 16 bits per bucket. So we lose a factor of ~3 on the number of buckets. In exchange, we don't lose as much accuracy when |A ^ B| << |A v B| and also do much better for multi-set intersections (where inclusion-exclusion becomes unwieldy).

As an aside, there are a bunch of other really cool Jaccard index fingerprinting methods out there that are asymptotically better even than HyperMinHash. But, they aren't as easy to work with and lack some of the other nice properties of MinHash.

Hi there! I'm the author of the paper the OP implemented, so I thought I'd give a bit more context.

In practice, combining together HLL and MinHash as they do for AdRoll gives the same kinds of estimation errors. However, using a raw MinHash data structure requires O(log n) space. If you are not space constrained, I second nemothekid and suggest just using off-the-shelf HLL intersection + MinHash libraries, such as the ones he links to.

The HyperMinHash algorithm, which the OP implemented in Golang, combines together the MinHash and HLL data structures so that we only need O(log log n) space, where n is the size of the union. In practice, the difference is between buckets of size log n + loglog n bits for HLL-MinHash and loglog n + 10 bits for HyperMinHash.

Given the constants involved, for n = 2^32, this is only a space savings of about 60% (37 bits vs 15 bits). However, this increases as n grows, so for n=2^64, it's 77% (70 bits vs 16 bits).

Thanks so much for producing a Golang implementation of our HyperMinHash paper (I'm the first author) [0] and pointing me to your Hackernews post!

As an aside, we also have a prototype Python implementation [1], but your implementation looks more efficient than ours, and I may start pointing people to your Github repo too.

[0]: https://arxiv.org/abs/1710.08436

[1]: https://github.com/yunwilliamyu/hyperminhash