Couldn't you build a composite data structure that internally makes use of both a bloom filter and one of these "opposite of a bloom filter" structures, and get the best of both worlds - no false positives and no false negatives?
Sadly not - instead you'd get disagreement from the two structures, with no way to resolve it.
If the bloom filter says 'yes I've seen it!', and the opposite filter says 'nope, not here', which is accurate? You know it's either a false-positive from the bloom filter or it a false-negative from the opposite filter, but that's the limit of your information. Effectively, you've partitioned your set into three: [definitely not, ambiguous, definitely seen].
If you want to know 100% of the items you've stored with full fidelity, you need to store information for all of them (e.g. in a hash table). Which is a valid thing to do, but requires a lot more memory than the author of this article was willing to use.
There's no free lunch; anything that can track a set perfectly is going to end up taking as much space as just maintaining it in a more straightforward way.
In the case of your specific suggestion, though, the problem is this: what if the bloom filter says "I've seen it (but could be lying)", and the "opposite" filter says "I've never seen it (but could be lying)"? Then you still have no idea whether the object is in the set.
> There's no free lunch; anything that can track a set perfectly is going to end up taking as much space as just maintaining it in a more straightforward way.
Unless there are regularities in the data that you can exploit.
This is an appealing idea and it took me a moment to see why it wouldn't work (other than the part where you simply don't have enough information).
It's correct to say that the bloom filter will produce no false negatives and the OOABF will produce no false positives, so if your OOABF returns true or your bloom filter returns false then you know for sure whether you've seen the item before. The trouble happens when your OOABF returns false and your bloom filter returns true, in which case you might have seen it before.
The thing is, when the bloom filter returns "I've seen it", you still need to resort to the array that has the actual keys.
A good way to look at the problem is that you have N keys to store (because you cannot have false positives). So with N keys, if you want less than sizeof(N)*N bytes, the only real answer is compression. So either you just discard data (what the OP does), or find a clever way to compress things.
The benefit is that you're only testing for existence, so that gives you some leeway. For instance, suppose you are getting random 8-byte user IDs. You could store, say, 1M of them in a hashtable, then take those items, sort them, and store deltas. Instead of 8 bytes per item, you'd only need 44 bits on average (2^64/1M) to store the differences. I believe this is what the OP suggested at the end of the article.
So, it really depends on the key types, and the penalty for forgetting an item. At a really high penalty (say, something that needs to perform an ACID SQL transaction), maintaining a compressed block of IDs is rather attractive. Whereas, if it's just sending an extra write to a high-perf write store, maybe it doesn't matter, and the OPs quick forgetful array is useful.
