A probabilistic set implementation in a fixed memory buffer, with an optional best-effort cleanup mechanism. The bigger the memory buffer, the less false positive outcomes of mem
.
In a standard bloom filter, element membership is encoded as bits being equal to 1 at indices obtained by hashing said element. In this implementation, elements are associated not to bits but to counters.
The countdown
function decrements the counter associated to an element. Hence, each counter corresponds to the number of calls to the countdown
function before they are removed from the filter, assuming no collision occurs.
To the best of our knowledge, the variant of bloom filters implemented in this module is new. In particular, this implementation does not correspond to counting bloom filters as described eg here: https://en.wikipedia.org/wiki/Counting_Bloom_filter
In order to emphasize the use of counters as a time-based garbage collection mechanism, we call this implementation a generational bloom filter.