<p>You just want a <a href="http://en.wikipedia.org/wiki/Cache">cache</a>, but are thinking about it in a weird way.</p>

CC BY-SA 3.0
2011-05-16T20:54:06.750Z
... 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
CC BY-SA 3.0
2011-05-16T20:55:20.527Z
(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
CC BY-SA 3.0
2011-05-16T15:29:44.403Z
2011-05-16T15:29:44.403Z
Craig Gidney
<p>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".</p>

<p>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 <em>number</em> of items stored. The <em>sizes</em> 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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-11-29T08:37:48.127Z
checkout http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/ - what's wrong this implementation/
Yehosef
CC BY-SA 3.0
2015-12-02T20:52:35.070Z
@Yehosef it's fine and may work for your needs, but you will notice that the author talks about there being a "few IDs that completely identify the event". So, what gets implemented is effectively still storing the entire object. So, it's a variant of a cache. A real "opposite of a bloom filter", if it existed, would not need to store entire objects.
pents90
CC BY-SA 3.0
2015-12-03T00:28:24.293Z
He mentioned a few ids that identify the event - not the entire object.  I just need to keep the "cache" on the session_id - not the entire interaction record.  But I hear that it's not the same type of approach as the bloom or a hyperloglog.
Yehosef
CC BY-SA 3.0
2017-04-02T12:43:13.277Z
In your "proof" you assume that there are an unlimited number of possible entries. However, there are cases where the set of possible entries is known in advance. For example, for garbage collection of a memory page: you know which entries it contains. Now you create a "gloom filter" that maps each possible entry to an index 0..n. Now when an entry is removed, set the bit a that index. When all bits are set, you can garbage collect the page. The "gloom filter" is a MPHF. To allow for false negatives, change the MPHF such that some entries are mapped to n+1.
Thomas Mueller
CC BY-SA 3.0
2017-04-03T20:43:03.293Z
@ThomasMueller Correct, I'm assuming the worst-case/adversarial case, which is standard CS theory point of view. It's true that if you only have a fixed set of N possible entries, then there are lots of straightforward solutions, with only log N space required for each item. The bloom filter has no such limitations, though.
pents90
CC BY-SA 3.0
2012-11-24T08:28:15.047Z
2012-11-24T08:28:15.047Z
pents90
<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2011-05-16T17:40:49.253Z
2011-05-16T17:40:49.253Z
Mohammad Alaggan
<p>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.</p>

CC BY-SA 3.0
2011-05-17T01:39:04.680Z
I've also wanted to try tries with string data, but my data tends to be packed binary structures.
JRideout
CC BY-SA 4.0
2023-09-06T01:00:15.823Z
The OP want's _no_ false positives, so this approach won't help.
Bennett McElwee
CC BY-SA 3.0
2011-05-17T01:30:36.887Z
2011-05-17T01:30:36.887Z
JRideout
<p>I think one can prove a lower bound stating that the above data structure cannot exist. Basically, if the data structure uses m bits, then a fixed bit-vector (representation of an input) can correspond to at most (((u-n)+ n eps) \choose (u-n)) sets by a counting argument. Given that 2^m times this number must be at least (u \choose n) (all sets must be represented), we get a lower bound which is basically very close to storing the set S precisely.</p>

CC BY-SA 3.0
2015-08-31T15:24:05.353Z
2015-09-02T17:52:06.843Z
2015-09-02T17:52:06.843Z
Mayank
<p>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.</p>

CC BY-SA 3.0
2011-05-16T20:56:29.027Z
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
CC BY-SA 3.0
2012-06-13T18:48:10.517Z
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. :)
awdz9nld
CC BY-SA 3.0
2012-06-13T18:54:51.100Z
Also note that only verbatim keys can be stored without introducing false positives (e.g. storing a hashed key)
awdz9nld
CC BY-SA 3.0
2011-05-16T12:12:41.663Z
2011-05-16T12:12:41.663Z
David Eppstein
<p>So, <a href="http://en.wikipedia.org/wiki/Bloom_filter">Bloom filters</a> 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. </p>

<p>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.</p>

<p>Yet I can't seem to find anything of the sort. The closest I've found are "<a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=4&amp;ved=0CDEQFjAD&amp;url=http%3A%2F%2Farxiv.org%2Fpdf%2Fcs%2F0607038&amp;ei=TfnQTbSQLIy5tweI-_X2DQ&amp;usg=AFQjCNH6cpseQMqDrkFsTOwMAaedZyUoKQ">retouched Bloom filters</a>", 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 <em>all</em> false positives, however. </p>

<p>Anyone seen anything like this? :)</p>

CC BY-SA 3.0
2011-05-16T10:35:25.227Z
Why not test membership of the complement of the set you are interested in using a Bloom filter, then invert the result?
Dave Clarke
CC BY-SA 3.0
2011-05-16T11:00:26.113Z
The complement of the set I am interested in is infinite. How would I store it?
Christopher Monsanto
CC BY-SA 3.0
2011-05-16T11:04:27.700Z
I see the problem (modern disks are not yet large enough).
Dave Clarke
CC BY-SA 3.0
2011-05-30T23:58:52.847Z
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
CC BY-SA 3.0
2012-07-24T23:47:38.893Z
@MarkReitblatt both Bloom filters and caches are probabilistic, and any combination thereof will be probabilistic, i.e. not able to achieve exact set membership testing. :)
awdz9nld
CC BY-SA 3.0
2012-10-22T14:38:06.207Z
http://stackoverflow.com/questions/635728/opposite-of-bloom-filter
Mauricio Scheffer
<ds.data-structures>
A probabilistic set with no false positives?
Christopher Monsanto
# A probabilistic set with no false positives?

(Asked by: username_0 on 2011-05-16)

So, [Bloom filters](http://en.wikipedia.org/wiki/Bloom_filter) 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](http://www.google.com/url?sa=t&source=web&cd=4&ved=0CDEQFjAD&url=http%3A%2F%2Farxiv.org%2Fpdf%2Fcs%2F0607038&ei=TfnQTbSQLIy5tweI-_X2DQ&usg=AFQjCNH6cpseQMqDrkFsTOwMAaedZyUoKQ)", 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? :)

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: Why not test membership of the complement of the set you are interested in using a Bloom filter, then invert the result?  
> **username_0**: The complement of the set I am interested in is infinite. How would I store it?  
> **username_1**: I see the problem (modern disks are not yet large enough).  
> **username_2**: 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.  
> **username_3**: @MarkReitblatt both Bloom filters and caches are probabilistic, and any combination thereof will be probabilistic, i.e. not able to achieve exact set membership testing. :)  
> **username_4**: http://stackoverflow.com/questions/635728/opposite-of-bloom-filter  

---

## 6 answers

### Answer by username_13 on 2011-05-16. Score: 30 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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. :)  
> **username_3**: Also note that only verbatim keys can be stored without introducing false positives (e.g. storing a hashed key)  

---

### Answer by username_6 on 2012-11-24. Score: 28

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.

> **Comments:**
> **username_7**: checkout http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/ - what's wrong this implementation/  
> **username_6**: @Yehosef it's fine and may work for your needs, but you will notice that the author talks about there being a "few IDs that completely identify the event". So, what gets implemented is effectively still storing the entire object. So, it's a variant of a cache. A real "opposite of a bloom filter", if it existed, would not need to store entire objects.  
> **username_7**: He mentioned a few ids that identify the event - not the entire object.  I just need to keep the "cache" on the session_id - not the entire interaction record.  But I hear that it's not the same type of approach as the bloom or a hyperloglog.  
> **username_8**: In your "proof" you assume that there are an unlimited number of possible entries. However, there are cases where the set of possible entries is known in advance. For example, for garbage collection of a memory page: you know which entries it contains. Now you create a "gloom filter" that maps each possible entry to an index 0..n. Now when an entry is removed, set the bit a that index. When all bits are set, you can garbage collect the page. The "gloom filter" is a MPHF. To allow for false negatives, change the MPHF such that some entries are mapped to n+1.  
> **username_6**: @ThomasMueller Correct, I'm assuming the worst-case/adversarial case, which is standard CS theory point of view. It's true that if you only have a fixed set of N possible entries, then there are lots of straightforward solutions, with only log N space required for each item. The bloom filter has no such limitations, though.  

---

### Answer by username_5 on 2011-05-16. Score: 17

You just want a [cache](http://en.wikipedia.org/wiki/Cache), but are thinking about it in a weird way.

> **Comments:**
> **username_0**: ... 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.  
> **username_0**: (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?  

---

### Answer by username_9 on 2011-05-16. Score: 3

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.


---

### Answer by username_10 on 2011-05-17. Score: 0

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.

> **Comments:**
> **username_10**: I've also wanted to try tries with string data, but my data tends to be packed binary structures.  
> **username_11**: The OP want's _no_ false positives, so this approach won't help.  

---

### Answer by username_12 on 2015-08-31. Score: 0

I think one can prove a lower bound stating that the above data structure cannot exist. Basically, if the data structure uses m bits, then a fixed bit-vector (representation of an input) can correspond to at most (((u-n)+ n eps) \choose (u-n)) sets by a counting argument. Given that 2^m times this number must be at least (u \choose n) (all sets must be represented), we get a lower bound which is basically very close to storing the set S precisely.


---

