3 ms·

False positives are possible but rare due to hash collisions. With a bloom filter, false negatives are impossible.

by biot 14y ago

ehsanu1 14y ago
Collisions not so rare for a small bucket.
anonymoushn 14y ago
False positives are not possible in the structure discussed in the OP.
- petercooper 14y ago
  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.
  - deleted 14y ago
    [deleted]
- biot 14y ago
  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.
  - eridius 14y ago
    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.
    - bbrtyth 14y ago
      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.
mason55 14y ago
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.
deleted 14y ago
[deleted]

False positives are possible but rare due to hash collisions. With a bloom filter, false negatives are impossible.

by biot 14y ago

False positives are possible but rare due to hash collisions. With a bloom filter, false negatives are impossible.

ehsanu1 14y ago

Collisions not so rare for a small bucket.

anonymoushn 14y ago

False positives are not possible in the structure discussed in the OP.

petercooper 14y ago
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.
- deleted 14y ago
  [deleted]
biot 14y ago
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.
- eridius 14y ago
  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.
  - bbrtyth 14y ago
    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.

mason55 14y ago

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.

deleted 14y ago

[deleted]