Bloom filters and sketches
A Bloom filter answers "is this in the set?" in a few bits per item, and it is allowed to be wrong — but only in one direction. If it says no, the answer is no, provably. If it says yes, it might be wrong, and how often it is wrong is not luck: it follows from three numbers you choose. These four pages show the structure one bit at a time over six words in a thirty-two-bit filter you can check by hand, then build real filters and count hundreds of thousands of real queries against them to see whether the textbook formula actually predicts what happens. Two more pages take the same idea somewhere else: counters instead of bits, so items can be deleted — and a grid of counters that estimates how often something appeared in a stream, with an error that can only ever be too high.
- Bloom filterAn array of bits and a handful of hash functions. Inserting an item sets k bits; querying reads them back. A zero means definitely absent; all ones means probably present.O(k)O(m) bits
- The false-positive rateBuilds real filters, queries them with hundreds of thousands of items known to be absent, counts the false positives, and plots the measured rate against the curve the standard formula predicts.O(k)O(m) bits
- Counting Bloom filterA counter in each slot instead of a bit, so items can be deleted. The cost is more space — and a way for false negatives to appear after all.O(k)O(m) bits
- Count-Min sketchA small grid of counters that estimates how often each item appeared in a stream, in space that does not grow with the stream. It can over-count, and can never under-count.O(d)O(d·w)
Measured curves against textbook bounds, for ordinary algorithms, are in the complexity plotter. Hashing's other great application — finding a pattern in text — is in String matching. The bits themselves are in Bits, floats, text and encodings.