Probabilistic data structures

Probabilistic structures trade exactness for bounded memory and fast operations. The correct choice starts with the query, the error direction, and the failure policy.

Do not treat "approximate" as one contract

These guarantees are not interchangeable. CMS does not answer membership exactly; HLL cannot return which elements exist; a Bloom or cuckoo filter does not count frequency.

End-to-end guarantee includes lifecycle

The theorem assumes more than an inner loop. Production correctness also depends on:

• stable hash functions, seeds, normalization, and namespace;
• parameter and counter/register widths;
• atomic rebuild and generation publication;
• overflow, saturation, and insertion-failure handling;
• merge compatibility and retry semantics;
• time-window/expiry semantics;
• concurrency control and durable authority.

A failed cuckoo insertion can create a false negative if the application pretends it succeeded. A wrapped CMS counter invalidates its bound. A partial Bloom rebuild can create false negatives. Adding one CMS partial twice double-counts it; HLL max-merge is idempotent.

Decision policy

Approximate negatives/positives may be used to reduce exact work only when the selected error direction is safe. Money, access control, legal retention, hard quota, irreversible deletion, and deduplication invariants need an exact authoritative path. Around thresholds, escalate rather than converting a confidence statement into a fact.

Sizing and measurement

Derive parameters from expected cardinality/mass and an explicit error budget. Monitor load, empirical error against samples, failed inserts, saturation, merge lag, and generation mismatch. Test adversarial/skewed inputs and restart/rebuild paths.

Diagram scenarios

The animation distinguishes Bloom, cuckoo, CMS, and HLL semantics, chooses by question, escalates to exact state, and fails closed on lifecycle faults.

Related concepts

Interactive scenarios