twitter/algebird — pull request #73 by echen (2012-12-15 13:31:32+00:00)
Title: Add cardinality estimation to Bloom filter.

I also switched `contains` to return an `ApproximateBoolean`.

Note:

1. The approximate cardinality estimate uses bounds (based on the number of "on" bits in the Bloom filter, rather than the expected number of collisions we were whiteboarding the other day) derived in [this paper](http://www.softnet.tuc.gr/~papapetrou/publications/Bloomfilters-DAPD.pdf). (I haven't worked through the details, but it looks like standard randomized algorithms stuff.)

2. But for the approximate `contains`, I don't have a good formula for the probability of a true positive, since the standard false probability formula depends on the true cardinality (which we don't know). So I do some "empirical bounding" to upper bound the true cardinality with high probability, which I then plug in. (I might generate some plots and such later.)
Instead, you could also simply plug in the cardinality estimate and its probability bound. I didn't do this because I think the cardinality probability bound is weak after some density point... But in retrospect, maybe this doesn't really matter, not sure. Thoughts (or a better formula?) welcome.