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

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. There is a very good analysis of this technique over at http://tech.adroll.com/blog/data/2013/07/10/hll-minhash.html http://tech.adroll.com/blog/data/2013/07/10/hll-minhash.html