Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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? :)

share|improve this question
    
Why not test membership of the complement of the set you are interested in using a Bloom filter, then invert the result? –  Dave Clarke May 16 '11 at 10:35
1  
The complement of the set I am interested in is infinite. How would I store it? –  Christopher Monsanto May 16 '11 at 11:00
9  
I see the problem (modern disks are not yet large enough). –  Dave Clarke May 16 '11 at 11:04
5  
If you had such a data structure, you could use it to "cheat" by using it in conjunction w/ a regular bloom filter and store exact set membership. –  Mark Reitblatt May 30 '11 at 23:58
2  
show 1 more comment

5 Answers

up vote 14 down vote accepted

One answer is to use a big hash table and when it fills up start replacing elements in it rather than finding (nonexistent) empty slots elsewhere for them. You don't get the nice fixed-rate of false answers that you do with Bloom filters, but it's better than nothing. I believe this is standard e.g. in chess software for keeping track of positions that have already been searched.

share|improve this answer
    
Thanks for the answer. Yeah, that is the obvious solution -- if it is also the standard solution, sounds like I'm out of luck. Oh well. –  Christopher Monsanto May 16 '11 at 20:56
    
This is called a Direct-mapped cache, and is commonly used in CPUs. (Any cache or lossy hash set fits the requirements to varying degrees). The error rate is a function of the hash function's distribution (avalanche) and the number of slots available in the cache/set - adjust accordingly. :) –  Martin Källman Jun 13 '12 at 18:48
    
Also note that only verbatim keys can be stored without introducing false positives (e.g. storing a hashed key) –  Martin Källman Jun 13 '12 at 18:54
add comment

You just want a cache, but are thinking about it in a weird way.

share|improve this answer
1  
... care to elaborate? Of course a cache would work, but that isn't ideal, hence a question about the state of the art in probabilistic data structures. To be more specific: caching techniques I know of require a lot of storage. The more cache levels, the more storage used. One could place a bound on the elements stored in the cache, do tricks with usage patterns, etc, but that still doesn't get anywhere near the space efficiency to false answer ratio that a Bloom filter provides. –  Christopher Monsanto May 16 '11 at 20:54
1  
(continued) That being said, I could be forgetting about an obvious caching technique that solves all of my problems. In that case, you could make explicit that technique instead of giving me a link to a general category on Wikipedia? –  Christopher Monsanto May 16 '11 at 20:55
add comment

The answer to this question is "no". To see why, we can think about a very extreme case, and how a regular bloom filter would work vs. a theoretical "Bizzaro World" bloom filter, which we can call a "gloom filter".

What is great about a bloom filter is that you can do one-sided tests for membership of items (with false positives) using a data structure that has a fixed size with respect to the probability of error and the number of items stored. The sizes of the items themselves don't matter at all. For example, if we had a bloom filter set up to store up to 1,000 items with less than 3% error, then we could store 1,000 slightly different versions of the entire corpus of Wikipedia, with one letter changed in each, and we would still get the metrics we want, and the data structure would be very tiny (less than a kilobyte). Of course, computing those hashes will be a challenge, but the principle still holds.

Now, consider storing those same massive strings in a gloom filter! We can only have false negatives now. So if we say "yes, that version of the entire corpus of Wikipedia is in this set", then we have to be absolutely right about that. That means hashing will not help us, as there will always be some other string that hashes to the same value. The only way to say "yes" and be sure is to store the whole string, or some equivalent data of the same length. We could always not store it and say "no", but eventually the error rate will catch up with us. The best we could do is compression, getting the size of the structure down to the product of the entropy of data stored and the accuracy we desire.

So, unfortunately the gloom filter doesn't exist. Caching is the only solution, but it is not really the opposite of a bloom filter, as its size will be proportional to the product of the quantity of information being stored and the desired accuracy rate of the filter. Of course, in many real-world scenarios, large data can be represented by an ID, so caching can be still be quite acceptable. But it's fundamentally different than the mighty bloom filter.

share|improve this answer
add comment

DISCLAIMER: I am not an expert in caches so this might be a naïve idea, and also may be a known idea which I've never heard of before. So excuse me if I fail to cite its reference (if it exists); and please inform me if there is a reference for it to edit the post and add it. (I am suspecting it might have a reference because it is so intuitive).

A quick solution after being inspired by Strilanc maybe to just keep a associative map of maximum $c$ entries (where $c$ is some constant) associating an item with the number of times it has has been seen. When the associative map is full and you meet a new item not in the map, flip a coin to add it or not. If you are to add it, then remove an item with probability inversely proportional to how many times it has been seen so far.

share|improve this answer
add comment

I've used AVL (and sometimes red-black) trees with partial items to act as as a filter with no false negatives. Use only the the first X bytes of the item when inserting or querying the tree. Because the data structure isn't probabilistic in form, there isn't the risk of a false-positive by bit collision. And unlike caching the entire item, this approach gives you a calculable maximum space. You can tune the rate of false positives by considering different prefix lengths / tree-depths in comparison to the cost of false positives and space.

share|improve this answer
    
I've also wanted to try tries with string data, but my data tends to be packed binary structures. –  JRideout May 17 '11 at 1:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.