Bloom filters and probabilistic data structures

In short: A Bloom filter checks in a space-saving way whether an element may be in a set. It answers either “definitely not” or “probably yes”, never wrongly “no”.

In more detail: The filter is a bit array with several hash functions. On insert k bits are set; on lookup all k bits must be set. False positives are possible, false negatives are not. Deleting is not possible (except in counting variants).

In Depth

• Space: About 10 bits per element at around 1 % error rate.
• Use: Databases (LSM trees save disk accesses), caches, browsers (malicious URLs), crawlers.
• HyperLogLog: Estimates the number of distinct elements with a few KB.
• Count-min sketch: Estimates frequencies.
• Trade-off: Memory and speed against accuracy.

See also: LSM tree and sorted string tables, Caching strategies and cache invalidation