So, Bloom filters are pretty cool -- they are sets that support membership checking with no false negatives, but a small chance of a false positive. Recently though, I've been wanting a "Bloom filter" that guarantees the opposite: no false positives, but potentially false negatives.
My motivation is simple: given a huge stream of items to process (with duplicates), we'd like to avoid processing items we've seen before. It doesn't hurt to process a duplicate, it is just a waste of time. Yet, if we neglected to process an element, it would be catastrophic. With a "reverse Bloom filter", one could store the items seen with little space overhead, and avoid processing duplicates with high probability by testing for membership in the set.
Yet I can't seem to find anything of the sort. The closest I've found are "retouched Bloom filters", which allow one to trade selected false positives for a higher false negative rate. I don't know how well their data structure performs when one wants to remove all false positives, however.
Anyone seen anything like this? :)