Ok Bloomer

An implementation of the OkBloomer algorithm, an autoscaling Bloom filter with ultra-low memory footprint for Python. Ok Bloomer employs a novel layered filtering strategy that allows it to expand while maintaining an upper bound on the false positive rate. As such, Ok Bloomer is suitable for streaming data where the size is not known a priori.

• Ultra-low memory footprint
• Autoscaling works on streaming data
• Bounded maximum false positive rate
• Open-source and free to use commercially

Installation

Install DNA Hash using a Python package manager, example pip:

pip install okbloomer

Parameters

Example Usage

from okbloomer import BloomFilter

filter = BloomFilter(
    max_false_positive_rate=0.01,
    num_hashes=4,
    layer_size=32000000,
)

filter.insert('foo')

print(filter.exists('foo'))

print(filter.existsOrInsert('bar'))

print(filter.exists('bar'))

print(filter.false_positive_rate())

True 

False

True

3.906249999999999e-27

References

• [1] A. DalPino. (2021). OkBloomer, a novel autoscaling Bloom Filter [link].
• [2] K. Christensen, et al. A New Analysis of the False-Positive Rate of a Bloom Filter.
• [3] A. Kirsch, et al. Less Hashing, Same Performance: Building a Better Bloom Filter, 2006.