Re:HyperLogSandwich
by t1m on Monday May 04, 2015 @06:34PM
(#9489709)
Note that intersections using HLLs don't work in general. The error rates become gigantic for sets that have small intersections, or whose cardinality differs greatly.
A general solution to cardinality estimations for intersections is to just use HLLs for union operations, and keep a MinHash sketch for each key as well to perform intersections.
Re:HyperLogSandwich
by iamwil on Tuesday May 05, 2015 @03:14AM
(#9491242)
HN is great. I was looking for something similar to HLL to do intersections, but couldn't find it because I didn't know what it was called. MinHash, apparently!
A general solution to cardinality estimations for intersections is to just use HLLs for union operations, and keep a MinHash sketch for each key as well to perform intersections.
There is a very good analysis of this technique over at http://tech.adroll.com/blog/data/2013/07/10/hll-minhash.html