addthis/stream-lib — pull request #54 by derekgr (2013-10-30 19:20:09+00:00)
Title: HyperLogLogPlus sparse merge produces incorrect results on some sets

I was recently were trying out the HyperLogLogPlus implementation, but on my real data I started finding many cases where merging small, sparse sets produced incorrect (too high) cardinality, even though the representation was never converted to normal.

Here's a simple failing test case that demonstrates the problem. If you continue merging in other sparse HLLP sets with intersection, the error continues to compound, increasing the amount over-counted by each time.

My expectation is that merging two sparse HLLPs, assuming the merge does not cause an overflow, produces a sparse HLLP result that has the exact cardinality of the union of the underlying sets, or possibly may undercount in the case of murmur hash collision.

cc @alindeman