Bloom filters are a data structure for testing set membership, which may have false positives but no false negatives. They're remarkably compact, and often usef

Bloom filters are a data structure for testing set membership, which may have false positives but no false negatives. They're remarkably compact, and often useful. The blog post talks about how to do even better in terms of compactness, through the clever use of Golomb coding. (And, incidentally, reduce the expected number of cache misses for a lookup.) Definitely worth a read, if any of that sounded interesting.