Cribra

What it is

Cribra is an interactive Bloom filter that can tell you a value is definitely absent or probably present, using far less memory than storing the set itself. The signature technique applies k hash functions via double hashing over a packed bit array, derives the optimal m and k from a target error rate, and adds false-positive and cardinality estimators, with tests led by its two defining properties - no false negatives, and an empirical false-positive rate that tracks theory. It is a from-scratch, dependency-light build you can download and run locally.

A from-scratch Bloom filter: k hashes by double hashing over a packed bit array, optimal m/k from a target error rate, and false-positive + cardinality estimators. 12 tests led by the two defining properties - no false negatives, and an empirical false-positive rate that tracks theory.