Skip to content

Latest commit

 

History

History
57 lines (40 loc) · 1.72 KB

README.md

File metadata and controls

57 lines (40 loc) · 1.72 KB
Raw

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

# Name Default Type Description
1 max_false_positive_rate 0.01 float The upper bound on the false positivity rate.
2 num_hashes 4 int The number of hash functions used, i.e. the number of slices per layer.
3 layer_size 32000000 int The size of each layer of the filter in bits. Ideal sizes can be divided evenly by num_hashes.

Example Usage

import okbloomer

filter = okbloomer.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.