bloomf
Bloom filters are memory and time efficient data structures allowing
probabilistic membership queries in a set.
A query negative result ensures that the element is not present in the set,
while a positive result might be a false positive, i.e. the element might not be
present and the BF membership query can return true anyway.
Internal parameters of the BF allow to control its false positive rate depending
on the expected number of elements in it.
Online documentation is available here.
Install
The latest version of bloomf
is available on opam with opam install bloomf
.
Alternatively, you can build from sources with make
or dune build
.
Tests
Some of the tests, measuring false positive rate or size estimation, might fail
once in a while since they are randomized. They are thus removed from dune runtest
alias.
To run the whole test suite, run dune build @runtest-rand
instead.
Benchmarks
Micro benchmarks are provided for create
, add
, mem
and size_estimate
operations. Expected error rate is 0.01.
They preform OLS regression analysis using the development version of
bechamel. To reproduce them, pinbechamel
then run dune build @bench
.
sha256=16409a1221e1d05a3d6b64ec0e5b302a60b6802cc573fdc243662e2fc85bd561
sha512=bc18e79cc782004edef88b24bc6ca586701294bd91c81ffc3de450df19f050e9e52b480980b74a5c38b7c70a3e9b4e94feca02007f1b661855868acf9cbdb245