41
$\begingroup$

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

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ The complement of the set I am interested in is infinite. How would I store it? $\endgroup$
    – Christopher Monsanto
    May 16, 2011 at 11:00
  • 11
    $\begingroup$ I see the problem (modern disks are not yet large enough). $\endgroup$
    – Dave Clarke
    May 16, 2011 at 11:04
  • 11
    $\begingroup$ 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. $\endgroup$
    – Mark Reitblatt
    May 30, 2011 at 23:58
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – awdz9nld
    Jul 24, 2012 at 23:47
  • 2
    $\begingroup$ stackoverflow.com/questions/635728/opposite-of-bloom-filter $\endgroup$
    – Mauricio Scheffer
    Oct 22, 2012 at 14:38

6 Answers 6

Reset to default
28
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Christopher Monsanto
    May 16, 2011 at 20:56
  • 2
    $\begingroup$ 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. :) $\endgroup$
    – awdz9nld
    Jun 13, 2012 at 18:48
  • $\begingroup$ Also note that only verbatim keys can be stored without introducing false positives (e.g. storing a hashed key) $\endgroup$
    – awdz9nld
    Jun 13, 2012 at 18:54
24
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ checkout somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - what's wrong this implementation/ $\endgroup$
    – Yehosef
    Nov 29, 2015 at 8:37
  • $\begingroup$ @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. $\endgroup$
    – pents90
    Dec 2, 2015 at 20:52
  • $\begingroup$ 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. $\endgroup$
    – Yehosef
    Dec 3, 2015 at 0:28
  • $\begingroup$ 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. $\endgroup$
    – Thomas Mueller
    Apr 2, 2017 at 12:43
  • $\begingroup$ @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. $\endgroup$
    – pents90
    Apr 3, 2017 at 20:43
16
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ ... 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. $\endgroup$
    – Christopher Monsanto
    May 16, 2011 at 20:54
  • 1
    $\begingroup$ (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? $\endgroup$
    – Christopher Monsanto
    May 16, 2011 at 20:55
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I've also wanted to try tries with string data, but my data tends to be packed binary structures. $\endgroup$
    – JRideout
    May 17, 2011 at 1:39
  • $\begingroup$ The OP want's no false positives, so this approach won't help. $\endgroup$
    – Bennett McElwee
    Sep 6 at 1:00
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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