Home > Coding > Bloom Filters  Bloom Filters  April 15th, 2007
A Bloom filter is a data structure for managing sets of values.
Bloom filters provide O(1) lookups and insertion and, perhaps
most importantly, provide an extremely compact representation of
the set of values being stored. The trade-off for this compact
representation is that the lookup operation can have false
positives. In other words, lookup(x) may return true even when x
isn’t in the set.  You might be wondering why we’d be willing or
able to tolerate false positives in set lookups. There are
actually lots of scenarios where this makes sense. For instance,
the original application of Bloom filters–spell checking on
limited-memory machines–remains a fine motivating example.  In
spell checking, a Bloom filter is used to store a dictionary of
correctly-spelled words. If lookup(word) returns false, the
spell checker flags word as a misspelling. False positives in
this application, e.g., lookup(‘notaword’) == True, results in
some misspellings goi