8 ms·
The Opposite of a Bloom Filter
- MichaelGG 14y agoTook me a few reads, but it's actually quite simple. You want a structure that can tell you something has been seen, but sometimes forgets, but will never incorrectly tell you something has been seen. Solution: an array. Hash the item to find its index, swap out what's there, and see if it is your item. If so, you know for sure it was previously placed. If not, then it might not have (it may have been forgotten). let arr = Array of key let contains_key key = let index = hash key % arr.length let prev_key = arr.swap[index, key] return prev_key = key The hash algorithm is crucial. Reducing forgetfulness is as simple as making the array longer. And he points out that if you can compress the keys, you can reduce storage size.
- jderick 14y agoSo it's just a cache?
- JonnieCache 14y agoA lot of things turn out to be "just" caches. Relatedly, the majority(?) of audio processing is just creative use of buffers.
- Dylan16807 14y agoSure, but this is a rather simple cache. Hash into bucket, LRU per bucket, stores the entire object. Nothing like the magic of a bloom filter that represents an object with 3-5 bits.
- deleted 14y ago[deleted]
- ajross 14y agoPretty much. There's a reason that there's no wikipedia page for this algorithm (where there is for Bloom Filter, of course) -- it's just a hash table without chaining (i.e. it simply drops collisions).
- NovaX 14y agoIts called a direct mapped cache: http://en.wikipedia.org/wiki/CPU_cache#Direct-mapped_cache http://en.wikipedia.org/wiki/CPU_cache#Direct-mapped_cache
- xianshou 14y ago@jderick: Specifically, it functions the same as a cache with a random removal policy, assuming a good hash function. So a cache and a Bloom filter are opposites: the first knows when something hasn't been seen, and might know when it has; the second knows when something hasn't been seen, and might know when it hasn't. The only difference between this and a normal cache is that we're dropping the values. On that subject, you might as well have an LRU valueless cache if locality is going to play a role.
- Ralith 14y ago> the second knows when something hasn't been seen, and might know when it hasn't. Don't think you meant that.
- IvarTJ 14y agoSo combining the two will not give you something that will make up for each of the ones weaknesses and always give a definite answer, but will give one of three answers – definite positive, maybe, and definitive negative. | P | M | N Bloom | X | X | Oppos | X | |
- dnc 14y ago> So combining the two will not give you something that will make up for each of the ones weaknesses and always give a definite answer True, although the probability of a false answer given that we combine them can be smaller from the probability of the same false answer in the case when we use each of them separately. This may be important in cases when the aversion to false answers is extremely high.
- davidkellis 14y agoCouldn'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?
- gwillen 14y agoThere'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.
- dllthomas 14y ago> 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.
- anonymoushn 14y agoThis 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.
- ajb 14y agoThis is useful. However, it is larger than a bloom filter, because a bloom filter needs one bit where this stores a value. I suspect that this asymmetry is unavoidable, but I can't prove it. Anyone?
- gms7777 14y agoThese sorts of filters have limits to accuracy and usefulness (and a definite tradeoff between memory requirements and accuracy). You can take both to the extreme, while still maintaining the definition: A structure that may report false positives, but no false negatives: A single bit set to 1 A structure that may report false negatives, but no false positives: A single bit set to 0 Obviously that's entirely useless, but I think it shows that you can't make any definitive proof of size requirements
- ajb 14y agoI don't think that shows that you can't make any definitive proof of size requirements. All it shows is that you have to make a statement about the accuracy. For example, it might be possible to prove that for all accuracies, an optimal bloom filter with a particular accuracy will always be smaller than an optimal inverse bloom filter of the same accuracy.
- usea 14y agoEven for 0% accuracy?
- gms7777 14y agoIntuitively, I think that might be the case. You have to define more specifically what you mean about accuracy here. Accuracy for the bloom filter would be probability of false positives. For the inverse it would be probability of false negatives. For a bloom filter, if you're targeting a false probability f with n items, you want k = lg(1)/f hash functions, and m = 1.44 k*n bits. That's the thing though. The bloom filter version scales up easily from the degenerate version (adding more bits increases accuracy). Unless I'm missing something, the inverse bloom filter doesn't scale up from the degenerate version in any natural way. This will nag at me now. I'm going to need to give this some thought. If I come up with any proof on mem reqs. I'll let you know.
- pdeuchler 14y agoThis may be naive of me, but wouldn't it be better to leverage your language's existing tools? For instance, in Python you would use a dict... >>> my_dict = {} >>> my_dict[item] = True #Insert an item >>> try: ... tmp = my_dict[item] ... print "Found" ... except KeyError: ... print "Not found" I can't imagine a custom implementation would be more efficient, though there may be other reasons to roll your own.
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- sbov 14y agoThe problem is your solution (as shown) will grow in memory forever. You can add code to get around that (e.g. expiration times), but it also might be easier (and have less memory usage) to write your own dict class that overwrites values when a collision occurs. Also, since the OP seems to be using java: if you can get away with storing a primitive data type in an array (e.g. array of int or long) you can save a lot of memory vs using a Set or Map.
- philsnow 14y agoPython dicts will grow and grow as you add more keys to them, but one of the constraints mentioned in the article (and implicitly included, because he's talking about a variation on a bloom filter) is that the data structure should not grow without bound. They wanted to use a fixed-size array. Also, in your example you're storing True as the value, but if you do that, you can't tell the difference between rbloom_array[hashfunc(item1)] and rbloom_array[hashfunc(item2)], if hashfunc(item1) == hashfunc(item2) (that is, they collide). You'd need to store the actual item in the data structure, not just a bit, and then you compare what you get out of the data structure to what you're trying to put in it. If the _items_ are equal then it's a duplicate and you can skip the write (to the database, from the example). If the items are not equal, you need to do the write.
- gojomo 14y agoSeems like a cache using open addressing but no probing, just instant eviction on any initial collision. So, could also consider adding probing to lessen destructive collisions (up to some chosen probing depth) while there are other unused slots, in still-constant average time. Or, any other choice-of-slots approach such as 'cuckoo hashing': http://en.wikipedia.org/wiki/Hash_table#Cuckoo_hashing http://en.wikipedia.org/wiki/Hash_table#Cuckoo_hashing Whether you'd want to pay that cost could depend on how soon you reach saturation within each reset period, after which 'every' insert results in an eviction. But if you were usually in one-for-one eviction mode, you might add a bit or more that hints 'age' or 'recent access' to probed items. Then each eviction could be biased towards an older/less-accessed value... taking more advantage of the clustering-in-time that was reported. And once you add that aging bit you might not need discrete full-restart periods ("hourly") at all: just make a useful proportion of older entries eligible for eviction each interval, maintaining a steady-state of full-array, evictions-biased-towards-older-entries.
- biot 14y agoFalse positives are possible but rare due to hash collisions. With a bloom filter, false negatives are impossible.
- ehsanu1 14y agoCollisions not so rare for a small bucket.
- anonymoushn 14y agoFalse positives are not possible in the structure discussed in the OP.
- petercooper 14y agoThough this is because they're storing an ID to check against and not anything inherent in the hashing or data structure which makes it not only the opposite of a bloom filter but rather different in spirit too.
- deleted 14y ago[deleted]
- biot 14y agoI re-read the article and I stand corrected. I had misread it as being just a store of the hash, but this stores the entire original object at the location identified by the hash of the object. And it needs to, because if even one byte is different out of a gigabyte of input data it must return false. That's horribly inefficient. With a bloom filter, you can take gigabyte-sized video files and determine if they have never been seen by the bloom filter. And the size of the bloom filter is fixed; choose the size based on expected inputs, desired accuracy, and so on and it doesn't grow based on the size of the objects being processed. With this implementation, it stores not only the hash of the video but the entire byte array of the video at the hash location in order to not have a false positive. So it's possible to have an opposite-of-a-bloom-filter with only 8 buckets, but it consumes terabytes of storage space because you're processing really massive files.
- cnlwsu 14y agoI had pretty much exact problem. We keep index of row keys in Cassandra on time partitioned data (by hour), but do not want to re-insert the index each time there is a piece of data. A ConcurrentLinkedHashMap (http://code.google.com/p/concurrentlinkedhashmap/ http://code.google.com/p/concurrentlinkedhashmap/) solved it easily. It does use more RAM though... but an insignificant amount on our heap.
- sprsquish 14y agoThis is almost exactly what our use case is. I slightly altered the implementation to be more GC friendly though: http://squishtech.posterous.com/addendum-to-the-opposite-of-a-bloom-filter http://squishtech.posterous.com/addendum-to-the-opposite-of-...
- paul 14y agoI'm skeptical that "hashing is much faster on an array the size of a power of two". Also, if memory is actually an issue, he should store hashes instead of full objects (assuming the byte arrays are more than 16 bytes).
- AlisdairO 14y agoIt's fairly common to keep array sizes bounded at a power of two, because when you take a hash you can use bitwise shifting instead of a modulus to determine the hash bucket to use. Depending on the performance of your hash function it can have a noticeable impact, although you're right that it's probably not a matter of 'much' faster.
- paul 14y agoI bet that there's no measurable difference in this code. It just bugs me to see so much unnecessary complication based on blindly imitating an optimization that maybe made sense 20 years ago.
- deleted 14y ago[deleted]
- fizx 14y agoI've noticed the difference between modulo and bitshift in java code written in the last five years. If it's getting 99.9+% cache hits, being used in an innermost loop, and jdk7 hasn't gotten around to JITing special cases in modulo, this could absolutely matter.
- spullara 14y agoIt was 10% faster to switch from modulo to & on a recent real world problem for me.
- brlewis 14y agoI believe you. There are two reasons I think paul's right in the context of hash tables. 1. If you're using a non-trivial hash function, one more modulo calculation at the end to get the actual memory address is not a big difference. 2. If you're using a trivial hash function, I bet for a lot of data sets you'll get fewer collisions with a hash table whose size is a prime number, canceling out any benefit from calculating the address slightly faster.
- scotty79 14y agoI'd implement it exactly like bloom filter but instead bits I'd use 0,1,2 0 means never touched. 1 means I've seen it, 2 means I've seen it more than once. True positive is when all places for given entry contain 1. Adding is incrementing all places (if they have value less than 2). Before putting new value in check if it's not already here. If it is don't add.
- bkirwi 14y agoThis doesn't work. If an object hashes to places abc, and each of a, b, and c were already incremented independantly by previous insertions, you would get a false positive.
- eridius 14y agoThat's not going to work at all. If I have an object A that hashes to bits 1, 5, 17, 24; an object B that hashes to bits 1, 5, 13, 15; and an object C that hashes to bits 2, 9, 17, 24; and I add objects B and C, then the filter will incorrectly think A has already been seen.
- scotty79 14y agoYou are right. I haven't properly thought that through.
- deleted 14y ago[deleted]
- afc 14y agoUm, wouldn't just a cache of the last N (based on memory available) items (or their hashes, whatever) just do the job, and do it better than his solution (which removes elements randomly based on collisions, rather than just removing the oldest element in the cache when it gets full, a much better approach given the time locality he describes)? The description in this article seems to add too much complexity ("the opposite of a bloom filter") for what really is just a simple cache (albeit, IMO, a relatively inefficient one for the problem he describes).
- webreac 14y agoHow to give fancy names to a simple algorithm using a hash map. I use perl a lot and as a result, this kind of algorithm occurs always.
- webreac 14y agoIn fact, it is simpler than a hash. The provided code is not complete (the limit to 1 hour is missing). Here is a full functional solution to its problem: perl -MDigest::MD5 -nle '($id,@data)=split;$t=time;$j=unpack("L", Digest::MD5::md5($id))%100;print join(" ",$id,@data) if $t-$h{$j}>3600 or $hi{$j} ne $id;$h{$j}=$t;$hi{$j}=$id' input
- mtrimpe 14y agoAnother option, in case you know the bounds of the parameter space (eg all natural numbers under 1000) you can implement this with a counting bloom filter that has every possible element pre-inserted.