Bloom filters

Learned about Bloom filters from Chris and Jonathan last night.

It's a probabilistic way of determining set membership: very fast, but with some frequency of error.

Given a Bloom filter, there's no way to enumerate the members of the set from the filter, but you can use the filter to test, quickly, whether something's in the set. There are no false negatives. The rate of false positives is configurable. If the universe is large, and the number of set members is small, this can be very useful.

(If the universe is small, then, obviously, you can enumerate the members of the set by just testing everyone. If the universe is large, and the number of set members is huge, then testing is inefficient and the size of the filter is huge.)