News for hackers. Stuff that matters.
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.