5 ms·

Author of the Library here: I can't fully agree that HyperLogLogs are good for intersections, that does not mean it can't be done, just there is always a high e

Author of the Library here: I can't fully agree that HyperLogLogs are good for intersections, that does not mean it can't be done, just there is always a high error rate. The easy way to do that is to maintain a separate MinHash sketch per HLL and use the Jaccard Index of several of those HLLs... an even more naive just use the Jaccard Index with the HLL registers but good luck getting good results out of that. This library is based on https://arxiv.org/pdf/1710.08436v4.pdf https://arxiv.org/pdf/1710.08436v4.pdf which has the benchmarks... Also I will be taking a stab at http://www.vldb.org/pvldb/vol11/p1097-nazi.pdf http://www.vldb.org/pvldb/vol11/p1097-nazi.pdf very soon :)

yunwilliamyu 8y ago
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.
- stochastic_monk 8y ago
  In my benchmarks, HyperLogLogs unilaterally outperform MinHash* by a constant factor, while Bloom Filters of the same size become more accurate than hyperloglogs in the 100-500kB range (though this number increases with the cardinalities of sets being compared). The biggest advantage a HyperLogLog has over MinHash and bloom filters is that it works well regardless of the sizes of the sets being compared, while MinHash is sensitive to differences in set size and bloom filters perform terribly in the small sketch domain. (These results aren't yet public, but they will be soon.) * Part of this might be issues with the original Flajolet et al. estimation algorithm. Ertl provides several improved methods in https://arxiv.org/pdf/1702.01284.pdf https://arxiv.org/pdf/1702.01284.pdf.

5 ms·

Author of the Library here: I can't fully agree that HyperLogLogs are good for intersections, that does not mean it can't be done, just there is always a high e

by seiflotfy 8y ago

yunwilliamyu 8y ago
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.
- stochastic_monk 8y ago
  In my benchmarks, HyperLogLogs unilaterally outperform MinHash* by a constant factor, while Bloom Filters of the same size become more accurate than hyperloglogs in the 100-500kB range (though this number increases with the cardinalities of sets being compared). The biggest advantage a HyperLogLog has over MinHash and bloom filters is that it works well regardless of the sizes of the sets being compared, while MinHash is sensitive to differences in set size and bloom filters perform terribly in the small sketch domain. (These results aren't yet public, but they will be soon.) * Part of this might be issues with the original Flajolet et al. estimation algorithm. Ertl provides several improved methods in https://arxiv.org/pdf/1702.01284.pdf https://arxiv.org/pdf/1702.01284.pdf.