liveBook · Manning

False positive

As explained in Advanced Algorithms and Data Structures

A false positive is an incorrect positive result indicating that an absent key is present or has an associated value.

A false positive is an incorrect positive result: a lookup reports that an absent key is present. In a Bloom filter, a negative result is certain, but a positive result requires verification because several keys may set the same bits. section 4.4.5 section 4.8.2

Collisions create false positives. With four bits and two hash functions, inserting values 1 and 2 can set bits 0 and 1; a lookup for absent value 3 returns true when its hashes point to those already-set positions. section 4.8.2

Handle positive results according to their cost and required accuracy:

  • Double-check a positive Bloom-filter result against the authoritative server or dictionary when correctness matters. section 4.6.1 section 4.7.3
  • Tune the filter’s memory allocation and number of hash functions for the expected capacity and tolerated false-positive probability. section 4.6.5
  • Accept false positives when their consequence is limited, such as a small reduction in cache performance. section 4.7.1

Email contact lookup

A local Bloom filter can reject contacts that are definitely absent. When it returns true, the application asks the server, because the local result may be a false positive. section 4.6.1

The false-positive rate rises as the filter holds more elements or uses less memory. A constructor can estimate the rate from the current element count, bit count, and number of hash functions; exceeding the planned capacity invalidates the expected precision. section 4.6.5 section 4.6.8

How Advanced Algorithms and Data Structures covers it

How deep it goes
Explains bit collisions, lookup handling, parameter tuning, and probability estimation, but stops short of a full mathematical derivation.
Examples
Demonstrates false positives with colliding four-bit hashes, email contact checks, cache filtering, and crawler URL tracking.
What you can do after
Apply false-positive trade-offs by sizing Bloom filters, verifying positive results, and judging whether an error’s consequence is acceptable.
How it connects
Connects false positives to Bloom filters, hash sets, hash tables, caches, crawlers, dictionaries, and Bloomier filters.

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 Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.