A Bloom filter screens set membership with definite negatives and possible positives. Follow a bit-array example, the false-positive approximation and safe trade-ID checks.
Bloom filter
A Bloom filter is a compact probabilistic data structure that tests whether a key belongs to a set. It can answer definitely absent or possibly present. In a market-data pipeline, that asymmetry can save expensive lookups for unseen identifiers while sending possible matches to an exact store for verification.
Unlike a hash table, a standard Bloom filter does not retain the keys or their values. It cannot return a trade record or list the identifiers inserted. Bloom's original paper frames the trade-off as a small memory-resident screen followed, when necessary, by a more expensive test.
How a collision becomes a “maybe”
Start with m zero bits. Use k repeatable hash mappings from each key to bit positions. Insertion sets those positions to one; querying checks the same positions. One zero is enough to reject membership. All ones mean a possible match, because other keys may have set those bits.
Take ten bits indexed 0–9 and two positions per key. These positions are assigned for teaching, rather than generated by cryptographic hashes or independent uniform draws.
Action
Positions checked or set
Result
Insert A
1 and 4
Set both bits to one
Insert B
4 and 7
Bit 4 stays one; set bit 7
Query absent C
1 and 7
Both one: false positive
Query absent D
1 and 9
Bit 9 is zero: definitely absent
Ten bits have ones at positions 1, 4 and 7 after inserting A at 1 and 4 and B at 4 and 7. Absent C checks 1 and 7 and returns maybe; absent D checks 1 and 9 and returns absent because bit 9 is zero.
The assigned positions expose the mechanism: C passes without ever having been inserted. A positive answer does not identify which keys set the bits.
The no-false-negative guarantee applies to successfully inserted keys queried with the same key encoding and hash mappings, with all required bits preserved. It does not cover missed updates, stale replicas, changed hashing, or corrupted storage.
Deletion is another boundary. Clearing A's bits would clear the shared bit 4 and make B fail its query. Ordinary bit clearing is unsafe. Counting Bloom filters use counters instead, with their own deletion and overflow requirements; see Broder and Mitzenmacher, §2.5.
What the false-positive rate measures
For n distinct inserted keys, an ideal model with independent uniform hash placements gives the familiar approximation
pFP≈(1−e−kn/m)k.
A particular bit remains zero with probability (1−1/m)kn in that model. Approximating this by e−kn/m and approximating occupancy by its mean leads to the expression above. Broder and Mitzenmacher, §2.1 explain both approximations.
At m=10, k=2, n=2, the expression gives 0.108688872…, or approximately 10.9%. This is an illustration of the formula, not the exact probability for the fixed tiny table above. C's assigned outcome is certain; the example specifies no random distribution over absent keys.
The rate means “positive given that the queried key is absent.” It is not the fraction of positive answers that are wrong; that fraction also depends on how often queries are for absent keys. With fixed m and k, inserting more distinct keys fills more bits and increases false positives. The name has no connection to filtering a time series or trading signal.
Use it as a screen, with a consistent exact store
Consider a fictional ingestion service checking trade IDs for duplicates. A positive Bloom result should trigger an exact ID lookup. Dropping a trade solely because the filter says “present” would discard some new trades. A negative can skip that lookup only when the filter includes all relevant committed IDs. Concurrent ingestion still needs an exact uniqueness or idempotency mechanism: two workers can both check an ID before either inserts it.
Current Redis documentation illustrates the interface distinction: membership returns either “may exist” or “definitely does not exist,” while filter creation accepts an intended capacity and false-positive target. Those settings need workload planning; they do not make membership exact. The bit array is also neither an occurrence counter nor an encryption mechanism.
