5 ms·
Useful library. I hope someone out there is writing one for Java as well.
by kgdinesh 9y ago
Useful library. I hope someone out there is writing one for Java as well.
- nemothekid 9y agoHLL intersections using MinSketch has been around for a while now, I remember writing a Go implementation a couple years back based on a AdRoll blog post (http://tech.adroll.com/blog/data/2013/07/10/hll-minhash.html http://tech.adroll.com/blog/data/2013/07/10/hll-minhash.html). They also open sourced their library (https://github.com/AdRoll/cantor https://github.com/AdRoll/cantor) as well. Generally in the big data space, libraries like this usually come out for Java first.
- yunwilliamyu 9y agoHi 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).