Inklings: a tumblelog

Scalable Bloom Filters (PDF)

…can adapt dynamically to the number of elements stored, while assuring a maximum false positive probability. The technique is based on sequences of standard bloom filters with increasing capacity and tighter false positive probabilities, so as to ensure that a maximum false positive probability can be set beforehand, regardless of the number of elements to be inserted.