News for hackers. Stuff that matters.
Re:The Opposite of a Bloom Filter by biot on Monday July 16, 2012 @02:31PM (#4251881)
False positives are possible but rare due to hash collisions. With a bloom filter, false negatives are impossible.
Re:The Opposite of a Bloom Filter by mason55 on Monday July 16, 2012 @04:23PM (#4252417)
False positives are possible but rare due to hash collisions

When there is a collision you check to see if the object living there is the one you're trying to store. If it's not then you assume negative. If it is the object you're checking then it's positive but it's a correct positive.

If it's not the object you're checking then you evict the object living there and put in the one you're checking, thus allowing the one you evicted to cause a false negative again.

The whole system works BECAUSE of intentional collisions. If there were no collisions it would just be a hashmap and you'd have unbounded data structure size.

Re:The Opposite of a Bloom Filter by anonymoushn on Monday July 16, 2012 @02:59PM (#4251976)
False positives are not possible in the structure discussed in the OP.
Re:The Opposite of a Bloom Filter by biot on Monday July 16, 2012 @05:18PM (#4252738)
I 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.

Re:The Opposite of a Bloom Filter by eridius on Monday July 16, 2012 @07:42PM (#4253290)
I'm pretty sure the structure was designed around relatively small objects. If you need to store large objects, then you can modify this structure to store the full un-masked hash instead of the object. Assuming no hash collisions (even with MD5 this should be a safe assumption if you're working with non-malicious data) the structure should behave identically.
Re:The Opposite of a Bloom Filter by bbrtyth on Tuesday July 17, 2012 @08:19AM (#4255342)
I can imagine the head scratching over this design decision 500 years in the future when everyone is an AI that has bajillions of files. Or one really unlucky guy tomorrow.
Re:The Opposite of a Bloom Filter by petercooper on Monday July 16, 2012 @04:19PM (#4252386)
Though 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.
Re:The Opposite of a Bloom Filter by ehsanu1 on Monday July 16, 2012 @02:50PM (#4251940)
Collisions not so rare for a small bucket.