twitter/algebird — pull request #105 by rjhall (2013-01-23 18:46:38+00:00)
Title: Optimizations for Large Bloom Filters

This PR has a few optimizations for making large BFs, e.g., to filter giant datasets in scalding. They are transparent except for a new dependency on a google jar which handles the sparse representation of a bitset.

The optimizations are:

1. The introduction of a new class "BFSparse" which gets created when summing BFItems together. This is basically the same as a BFInstance except the underlying BitSet uses a different representation. This allows for a smaller memory footprint, and the time to make additions is not greatly impacted. However this is slower on lookups, therefore the BFSparse is lazily made into a BFInstance when a lookup happens.

2. BFInstance.contains is sped up, since the hashes for the input string usually consist of a few bits only, its better to iterate over those and test containment, rather than to use BitSet & and ==, the latter of which is very slow on a large BitSet.

3. Store the result of calling BitSet.size on the BFInstance, as this call is very expensive on a large BitSet.