liveBook · Manning

False positive

As explained in The Coder Cafe

A false positive is a membership result that reports possible presence even though the queried element was not inserted.

A false positive is a membership result that reports that an element may be present even though it was never inserted. Bloom filters produce false positives when hash collisions make the queried positions appear set; they never produce false negatives. section 6.13.2 section 6.13

False positives are the cost of a compact membership check. A bloom filter can safely identify elements that are definitely absent, but a positive result requires another check when existence must be guaranteed. Hashmaps or B-trees are better when false positives are unacceptable. section 6.13.4 section 6.13

The false-positive rate depends on how the bloom filter is configured and used:

  • Adding more elements to a fixed-size filter raises the false-positive rate, so estimating the expected element count is important. section 6.13.5
  • The relevant parameters are the number of hash functions, expected elements, and bitvector size. section 6.13.5
  • False positives are acceptable when a positive result only triggers a more expensive verification; they are unsuitable when membership requires a strict guarantee. section 6.13.4

Estimating a rate

For a bloom filter expecting 1,000 elements with a 10 KB bitvector and two hash functions, the estimated false-positive rate is about 3.15%. To target at most 0.1% with 1,000 elements and two hash functions, the required bitvector is approximately 62,240 bits, or slightly less than 8 KB. section 6.13.5

Figure 6.1 A bloom filter can return all the options except for false negatives.

Use the outcome diagram to distinguish definite absence, possible presence, and the false-negative result a bloom filter does not return. section 6.13

How The Coder Cafe covers it

How deep it goes
Defines collision-based behavior, identifies configuration parameters, and works through rate and sizing calculations.
Examples
Uses bloom-filter outcome diagrams, parameterized probability examples, and applications in databases, CDNs, blockchains, and network security.
What it assumes
Assumes basic familiarity with set membership and hashing while introducing bloom-filter outcomes and probability parameters.
What you can do after
Evaluate bloom-filter reliability and configure bitvector size from an expected element count and tolerable false-positive rate.
How it connects
Connects false positives to bloom filters, hash collisions, hash functions, bitvectors, hashmaps, and B-trees.

Also explained in

Compare how 26 books explain false positive →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of The Coder Cafe. The section links point to the parts of the book it draws on.