Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in a significant memory saving over a hash table. The main feature of a Bloom filter, which it shares with a hash table, is that it always says "not new" if an item is not new, but there is a non-zero probability that an item will be flagged as "not new" even when it is new.

Is there an "anti-Bloom filter", which has the opposite behaviour?

In other words: is there an efficient data structure which says "new" if an item is new, but which might also say "new" for some items which are not new?

Keeping all the previously seen items (for instance, in a sorted linked list) satisfies the first requirement but may use a lot of memory. I am hoping it is also unnecessary, given the relaxed second requirement.


For those who prefer a more formal treatment, write $b(x) = 1$ if the Bloom filter thinks $x$ is new, $b(x) = 0$ otherwise, and write $n(x) = 1$ if $x$ really is new and $n(x) = 0$ otherwise.

Then $Pr[b(x) = 0 | n(x) = 0] = 1$; $Pr[b(x) = 0 | n(x) = 1] = \alpha$; $Pr[b(x) = 1 | n(x) = 0] = 0$; $Pr[b(x) = 1 | n(x) = 1] = 1 - \alpha$, for some $0 < \alpha < 1$.

I am asking: does an efficient data structure exist, implementing a function $b'$ with some $0 < \beta < 1$, such that $Pr[b'(x) = 0 | n(x) = 0] = \beta$; $Pr[b'(x) = 0 | n(x) = 1] = 0$; $Pr[b'(x) = 1 | n(x) = 0] = 1 - \beta$; $Pr[b'(x) = 1 | n(x) = 1] = 1$?


Edit: It seems this question has been asked before on StackExchange, as http://stackoverflow.com/questions/635728 and http://cstheory.stackexchange.com/questions/6596 with a range of answers from "can't be done" through "can be done, at some cost" to "it is trivial to do, by reversing the values of $b$". It is not yet clear to me what the "right" answer is. What is clear is that an LRU caching scheme of some sort (such as the one suggested by Ilmari Karonen) works rather well, is easy to implement, and resulted in a 50% reduction in the time taken to run my code.

share|improve this question
    
For some reason, I'm tempted to say that this is very similar to the problem that caches and cache placement algorithms attempt to solve. Consider a cache using least-frequently-used (LFU) replacement. A theoretically optimal but impossible replacement algorithm would be to evict the one that you won't see again for the longest time, same as for caches. I suppose caching relies on some assumptions about the nature of the distribution that may not hold generally, but it's worth considering whether this applies. –  Patrick87 Apr 25 at 21:45
    
You may be interested in the following talk: Satisfiability-based set membership filters –  Kaveh Apr 26 at 21:04
    
@Kaveh: thanks for the pointer, will watch. –  András Salamon Apr 26 at 21:54

4 Answers 4

up vote 8 down vote accepted

Going with Patrick87's hash idea, here's a practical construction that almost meets your requirements — the probability of falsely mistaking a new value for an old one is not quite zero, but can be easily made negligibly small.

Choose the parameters $n$ and $k$; practical values might be, say, $n = 128$ and $k = 16$. Let $H$ be a secure cryptographic hash function producing (at least) $n+k$ bits of output.

Let $a$ be an array of $2^k$ $n$-bit bitstrings. This array stores the state of the filter, using a total of $n2^k$ bits. (It does not particularly matter how this array is initialized; we can just fill it with zeros, or with random bits.)

  • To add a new value $x$ to the filter, calculate $i \,\|\, j = H(x)$, where $i$ denotes the first $k$ bits and $j$ denotes the following $n$ bits of $H(x)$. Let $a_{i} = j$.

  • To test whether a value $x'$ has been added to the filter, calculate $i' \,\|\, j' = H(x')$, as above, and check whether $a_{i'} = j'$. If yes, return true; otherwise return false.

Claim 1: The probability of a false positive (= new value falsely claimed to have been seen) is $1/2^{n+k}$. This can be made arbitrarily small, at a modest cost in storage space, by increasing $n$; in particular, for $n \ge 128$, this probability is essentially negligible, being, in practice, much smaller than the probability of a false positive due to a hardware malfunction.

In particular, after $N$ distinct values have been checked and added to the filter, the probability of at least one false positive having occurred is $(N^2-N) / 2^{n+k+1}$. For example, with $n=128$ and $k=16$, the number of distinct values needed to get a false positive with 50% probability is about $2^{(n+k)/2} = 2^{72}$.

Claim 2: The probability of a false negative (= previously added value falsely claimed to be new) is no greater than $1-(1-2^{-k})^N \approx 1-\exp(-N/2^k) < N/2^k$, where $N$ is the number of distinct values added to the filter (or, more specifically, the number of distinct values added after the specific value being tested was most recently added to the filter).


Ps. To put "negligibly small" into perspective, 128-bit encryption is generally considered unbreakable with currently known technology. Getting a false positive from this scheme with $n+k=128$ is as likely as someone correctly guessing your secret 128-bit encryption key on their first attempt. (With $n=128$ and $k=16$, it's actually about 65,000 times less likely than that.)

But if that still leaves you feeling irrationally nervous, you can always switch to $n=256$; it'll double your storage requirements, but I can safely bet you any sum you'd care to name that nobody will ever see a false positive with $n=256$ — assuming that the hash function isn't broken, anyway.

share|improve this answer
1  
Not only can the probability be made comparable to that of hardware malfunction; it can also be made comparable to the probability of someone guessing your RSA key for SSH login on the first try. IMO the latter conveys the practicality of your solution more than the former. –  R.. Apr 27 at 3:29
    
+1 Very nice - my understanding is that this solves the space efficiency problem by allowing some (very small) chance of incorrectly answering "not new" when the item is, in fact, new. Very practical, and good analysis. –  Patrick87 Apr 28 at 15:40
1  
Claim 1 is just stating that a decent hash function has a low probability of collisions. This is true in practice already if $n+k$ is at least 50 or so. For my application, $n=44$ and $k=20$ works great with a simple 64-bit, non-cryptographically secure, but fast hash function. –  András Salamon Apr 28 at 18:24
    
@AndrásSalamon: True, although a secure cryptographic hash function actually provides a slightly stronger guarantee: namely, that it is impractical to find colliding inputs even if you try to deliberately look for them. With a sufficiently large $n$ (e.g. $n=128$ as I suggested above), this means that storing the full data is unnecessary even if the cost of a false positive is high and even if there might be an active adversary attempting to find one. Of course, if you don't need quite so strong a guarantee, a somewhat higher collision risk can be acceptable. –  Ilmari Karonen Apr 28 at 19:29

What about just a hash table? When you see a new item, check the hash table. If the item's spot is empty, return "new" and add the item. Otherwise, check to see if the item's spot is occupied by the item. If so, return "not new". If the spot is occupied by some other item, return "new" and overwrite the spot with the new item.

You'll definitely always correctly get "New" if you've never seen the item's hash before. You'll definitely always correctly get "Not New" if you've only seen the item's hash when you've seen the same item. The only time you'll get "New" when the correct answer is "Not New" is if you see item A, then see item B, then see item A again, and both A and B hash to the same thing. Importantly, you can never get "Not New" incorrectly.

share|improve this answer
1  
I suppose this sort of ignores the space efficiency issue, or rather, is significantly less efficient than a bloom filter would be, since a bloom filter really only needs a bit per bucket, and this needs as much space per bucket as it takes space to represent the items. Oh well... unless the universe is finite (as in Wandering Logic's answer) I think you probably can't get very close to a bloom filter's space efficiency. –  Patrick87 Apr 25 at 22:51
    
Personally, I think your answer is way better than mine. A bloom filter is not just a bit per bucket if you want probabilities better than 50%. It also is a fixed size and once you fill it more than half full the probability of false positives increases precipitously. There's no convenient way to expand it, no convenient way to use it as a cache and no convenient way to delete elements. I'll take a hash table every time. –  Wandering Logic Apr 26 at 2:42
    
@WanderingLogic Using a small saturating counter instead of single bit allows deletion to be supported (at the cost of capacity and only if the counter is not at the maximum, obviously). –  Paul A. Clayton Apr 26 at 3:17

No, it is not possible to have an efficient data structure with these properties, if you want to have a guarantee that the data structure will say "new" if it is really new (it'll never, ever say "not new" if it is in fact new; no false negatives allowed). Any such data structure will need to keep all of the data to ever respond "not new". See pents90's answer on cstheory for a precise justification.

In contrast, Bloom filters can get a guarantee that the data structure will say "not new" if it is non-new, in an efficient way. In particular, Bloom filters can be more efficient than storing all of the data: each individual item might be quite long, but the size of the Bloom filter scales with the number of items, not their total length. Any data structure for your problem will have to scale with the total length of the data, not the number of data items.

share|improve this answer
    
Also see the accepted answer, since the question there is the same –  Joe Apr 26 at 18:27
    
-1 You should probably qualify what you mean when you say it's not possible. Clearly it's possible to do it efficiently, and it's also possible to do it with a low rate of error, so striking some balance in a given implementation should be feasible... in particular, it would be useful to explain exactly what is meant by "all of the data ever", since this isn't strictly necessary to satisfy the question's ask. False negatives - responding "new" when the answer should be "not new" - are allowed here, so not all data need be kept. –  Patrick87 Apr 28 at 15:47
1  
This answer is perfectly reasonable, and seems to address the letter of my question, but perhaps not the spirit. –  András Salamon Apr 28 at 18:28
    
@D.W. Thanks for taking the time to update the answer. I'm inclined to leave this as an answer now, although I still object to the language used when describing the inefficiency of anti-bloom filters, in addition to thinking it would be best to elaborate a bit more on the "details" referenced... leaving the -1 for now. Cleaned up some obsolete comments. –  Patrick87 Apr 29 at 5:10
    
@D.W. By "false negative", I intend responding "new" when the answer ought to have been "not new". (Somewhat counterintuitively, "not new" is the positive case here.) You do not need to save "all of the data ever" to pull this off, although I'm inclined to believe you do need to do save whole elements (just not all elements - unless you're willing to accept a hypothetically meaningful chance of error, as per the other answer to the question here.) –  Patrick87 Apr 29 at 5:18

In the case where the universe of items is finite, then yes: just use a bloom filter that records which elements are out of the set, rather than in the set. (I.e., use a bloom filter that represents the complement of the set of interest.)

A place where this is useful is to allow a limited form of deletion. You keep two bloom filters. They start out empty. As you insert elements you insert them into bloom filter A. If you later want to delete an element you insert that element into bloom filter B. There is no way to undelete. To do a lookup you first lookup in bloom filter A. If you find no match, the item was never inserted (with probability 1). If you do find a match the element may (or may not) have been inserted. In that case you do a lookup in bloom filter B. If you find no match, the item was never deleted. If you do find a match in bloom filter B, the item was probably inserted and then deleted.

This doesn't really answer your question, but, in this limited case, bloom filter B is performing exactly the "anti-bloom filter" behavior you are seeking.

Real Bloom filter researchers use much more efficient ways of representing deletion, see Mike Mitzenmacher's publication's page.

share|improve this answer
    
In this question, we are processing items, and there are no deletions. There is no meaningful way to store the compliment without having to remove items from the bloom filter –  Joe Apr 26 at 18:30
1  
@Joe: I agree that the problem is insoluble in general, so restricted my answer to the case where the complement was finite and small. –  Wandering Logic Apr 26 at 19:42

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.