DFIELDSOLUTIONS

Free software

LabCribra: Probably yes. Definitely no

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.

Free software1 sections · 2 min readBy Dezső Mező.mdFree softwareCribra

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.

01About the app

Probabilistic data structures

What to take away

  • 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.
  • Download: Cribra (ZIP)
We build this for clientsFull-stack

Read the full write-up

More from the lab

Browse all entries

Want this looked at on your own system?Start a conversation

5.0
“New shop, more orders in the first week.”Müller Márk · GeekCornerManaging Director · Hungary