Membership Filters & Duplicate Detection

Answering Have We Seen This Before?

Imagine a receptionist with a very long guest list and a tiny desk card. The card can quickly say “definitely not on the list” or “possibly on the list; check the register.” It cannot reliably name every guest. A membership filter plays that role for a large set of keys. Its useful trade is a small amount of memory for occasional false positives: an absent key may appear present. Under the right update rules, an inserted key will never appear absent.

Take an eight-position bit card, initially all zero. Suppose inserting A marks positions 1 and 4, and inserting B marks 4 and 6. The marked positions are now 1, 4, and 6. An absent C whose two positions are 1 and 6 looks present: a false positive. An absent D whose positions are 1 and 2 is definitely absent because position 2 is zero. This example depends on the positions supplied by the hash functions; a real guarantee averages over their specified random choice for a fixed collection of keys.

Why does this matter? A cache may use the card to avoid a fruitless disk lookup, a security service may narrow candidates for an authoritative blocklist, and an event pipeline may screen potential duplicates before checking a durable ID store. The last check is crucial: treating “possibly seen” as proof of a duplicate can discard a new event. We will distinguish the set represented by the filter, the keys seen in a stream, and the records actually committed by a system.

Bits, Fingerprints and One-Sided Error

Fix a universe $U$ and represented set $S\subseteq U$ with $n$ distinct keys. A membership query answers whether $x\in S$. For a conventional Bloom filter, keep $m$ bits and use $k$ hash positions per key. Insertion sets all $k$ positions to one; a query is negative if any of those positions is zero, otherwise positive. Bits never return to zero in the basic insert-only design. Therefore every key successfully inserted remains positive deterministically, even when positions collide. For a fixed absent query, a stated false-positive probability is over the random choice of hashes under a specified input and query model. It does not say that every absent key is unlikely to be positive simultaneously.

Deletion changes the contract. A counting Bloom filter replaces bits with small counters, increments the positions on insertion, and decrements them only for a key whose insertion is known and whose multiplicity is tracked appropriately. A membership query checks whether all relevant counters are positive. Counter overflow, a missing update, or deleting an absent key based on a false positive can produce false negatives. A simple Bloom filter cannot safely delete by clearing bits shared with other keys.

Fingerprint-based alternatives store compressed tags rather than the entire key. A cuckoo filter stores a fingerprint in one of two candidate buckets and may move existing fingerprints during insertion; a failed displacement at high load needs an explicit retry, growth, or rejection policy. An XOR filter generally builds an array for a fixed key set so the XOR of a query's addressed cells agrees with its fingerprint on members. Construction may need a new seed or larger table if peeling fails; ordinary incremental insertion or deletion is not part of that static contract. A quotient filter stores a hash's quotient and remainder with metadata that allows runs of related fingerprints to be found; capacity, clustering, and the chosen variant govern update costs and deletion. Fingerprint matches can be false positives, so the precise rates depend on construction and load, not just a label such as “10-bit fingerprint.”

flowchart TD
    S["Committed set S"] --> U{"Update model"}
    U -->|Insert only| B["Bloom: set k bits"]
    U -->|Known insert and delete| C["Counting or dynamic variant"]
    U -->|Static batch| X["Build XOR filter"]
    B --> Q["Query all k positions"]
    C --> Q
    X --> F["Compare fingerprint"]
    Q --> N["Any zero: absent"]
    Q --> P["All positive: possibly present"]
    F --> P
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class S,U navy; class B,C,X teal; class Q,F purple; class N,P crimson;

Deriving False Positives and Capacity Limits

Assume $k$ independent uniform positions for each of $n$ distinct inserted keys in an $m$-bit array, chosen with replacement. A particular bit avoids one position with probability $1-1/m$, so its probability of remaining zero after $kn$ position choices is exactly $(1-1/m)^{kn}$ under this ideal model. Thus its expected occupancy fraction is $q=1-(1-1/m)^{kn}\approx1-e^{-kn/m}$. The familiar false-positive design formula $p_{\mathrm{FP}}\approx(1-e^{-kn/m})^k$ additionally treats the tested positions and occupancy as if they were suitably independent and concentrated. For finite $m$, this is an approximation, not an exact consequence of the one-bit expectation: the bit states are correlated. Measure or bound actual rates when these approximations or the hash construction matter.

Minimizing that approximate expression with $m$ and $n$ fixed gives $k_{\mathrm{opt}}\approx(m/n)\ln2$. At this point roughly half the bits are set. Solving for a desired approximate false-positive target $p$ gives $m\approx-n\ln p/(\ln2)^2$ bits. For $n=1{,}000$ and $p=0.01$, this is about $9{,}585$ bits, roughly $1{,}199$ bytes, and $k\approx6.64$, so evaluate the nearby integers $6$ and $7$. These figures omit metadata, alignment, hash seeds, and any operational headroom. If actual unique keys exceed $n$, occupancy and false positives rise; repeated insertion of the same key does not create $k$ fresh independent positions in a deterministic Bloom filter.

For the eight-bit warm-up, after A and B the occupied set is $\{1,4,6\}$. It is tempting to subtract A by clearing 1 and 4, but B also needs 4, so querying B then finds a zero and gives a false negative. Counting bits instead yields counts at positions 1, 4, 6 of $1,2,1$ if the two positions per key are distinct. Decrementing A correctly leaves $0,1,1$, preserving B. A mistaken deletion of C, whose positions 1 and 6 only look present, would decrement counters belonging to A and B and can damage the invariant.

A filter's headline rate is often the probability for one fixed absent query, not the probability that a whole query workload has no false positives. If a workload contains $Q$ fixed absent queries each with false-positive probability at most $p$, the union bound gives probability at most $Qp$ of at least one false positive, capped at 1; it needs no independence. An attacker who adaptively probes a public filter and then selects a known positive is not covered by that fixed-query statement. For high-consequence decisions, the positive branch must be verified against authoritative state.

flowchart TD
    A["m bits; k positions; n distinct keys"] --> Z["One bit stays zero with (1−1/m)^(kn)"]
    Z --> O["Expected occupied fraction q"]
    O --> P["Approximate nonmember rate q^k"]
    P --> K["Choose k near (m/n) ln 2"]
    K --> M["Budget m for target rate and headroom"]
    O --> D{"Need deletions?"}
    D -->|Yes| C["Count positions; verify actual membership"]
    D -->|No| B["Keep monotone bits"]
    C --> F["Overflow or wrong deletion breaks guarantee"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class A,Z navy; class O,P,K,M,B teal; class F crimson; class D,C purple;

Cache Admission, Abuse Lists and Deduplication

Approachable cache. A cache keeps an exact database of stored objects behind a Bloom filter. When a requested key tests negative, the cache can skip a pointless database lookup if the filter is complete and current. A positive goes to the database: it may be an actual hit or a false positive that costs one extra lookup. This arrangement preserves correctness while reducing work. During asynchronous insertion, “complete and current” must be defined: if the database contains a key before the filter receives its update, a negative can wrongly bypass that record.

Production event deduplication. Suppose a pipeline ingests $50$ million events per day, expects $5$ million unique event IDs in a rolling epoch, and can budget roughly $1$ MiB of filter bits per million IDs at a chosen false-positive rate. The durable ID store remains authoritative. A negative can proceed to an exact insert path, while a positive triggers a lookup or an atomic insert-if-absent; neither branch should drop an event merely because of the filter. The actual protocol must handle races, retries, crashes, and epoch rotation. Bloom bits cannot remove old keys safely; rotate whole epoch filters or choose a deletion-capable design with correct multiplicities. Measure unique IDs, occupancy, extra lookups, update lag, and false negatives caused by system inconsistency separately from theoretical hash false positives.

Abuse list and malicious probing. A service screens incoming account IDs against a blocklist. A false positive must not by itself deny service, because an innocent ID may collide; positives should be checked against an authoritative list. If an attacker can probe the public filter and choose IDs that test positive, the fixed-query false-positive rate does not limit the attacker-selected workload. If a list changes, stale replicas can also produce negatives for recently blocked IDs or positives for removed ones. State freshness, authorization and threat assumptions before using “no false negatives” as an operational promise.

Select a Filter Under Real Constraints

Choose a filter by the permissible mistake, population size, mutation pattern, and action taken after a positive result. The same approximate membership answer can be safe as a lookup precheck and unsafe as a final security or financial decision. These exercises make each premise and failure path explicit.