3 ms·

Pretty close. Except 1) you generate multiple hashes for a particular value, thus setting multiple bits for a value 5) when this happens, you use a lar

Pretty close. Except 1) you generate multiple hashes for a particular value, thus setting multiple bits for a value 5) when this happens, you use a larger filter 6) You can also determine with 100% confidence that a value isn't in the set. Other than that, I think you have a good idea of what it's about. Once I learned about this, I got tons of great ideas. Right now, I think it would be cool to construct a bloom filter for detected bot users on twitter. You could make a plugin that marked tweets from probable bot-users as such without storing the whole db on disk, and without making tons of network requests.

afonsotsukamoto 9y ago
I do believe on the 100% confidence, but when you have full filter is that still meaningful? As in - are there still any gains on using a bloom filter in this case? I know that is sort of a corner case, but in that situation the 100% confidence case happens 0% of the times which makes the filter a bit useless - no? Just trying to understand what are the limitations as been super curious about bloom filters for a long time
- tekromancr 9y ago
  You are correct. The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what the ideal size is, it depends on the desired probability of false positives, but an optimally large filter for the data you are using will have some empty bits.
  - bane 9y ago
    Here's a helpful calculator, it will even tell you the optimal number of hash functions. All you have to know is the expected cardinality of the set. https://hur.st/bloomfilter https://hur.st/bloomfilter
    - afonsotsukamoto 9y ago
      ah! ok - I just had a "mind bending" moment after looking at the calculator + tekromancr's response. I thought we would want to control the number of hash functions (k) and the number of items (n) but I guess the most common use case will be to set the allowed probability of a false positive for the number of allowed items and let the "system" control the k and m (hash functions and bits in the filter) Enlightening! One question remains though - since the number of bits (m) is a function of the probability of false positives (p) and the number of hash functions (k) is a function of the number of bits and the number of items (n), does it mean that once we start a bloom filter we can't update the number of items or the desired probability of false positives? My assumption is that if we change p, then m will change, which would make the k functions "obsolete" as they're being "mapped" to a new sized m. Same for n, which would change the k functions, making it so that a new item would be hashed differently, making m hits/misses obsolete again. Might be missing something here though. Either way, I still find bloom filters a fascinating data structure.
      - tekromancr 9y ago
        Nope, I think you got it. My understanding is that if you want to change the params, you need to rebuild the filter.

afonsotsukamoto 9y ago

I do believe on the 100% confidence, but when you have full filter is that still meaningful? As in - are there still any gains on using a bloom filter in this case? I know that is sort of a corner case, but in that situation the 100% confidence case happens 0% of the times which makes the filter a bit useless - no? Just trying to understand what are the limitations as been super curious about bloom filters for a long time

tekromancr 9y ago
You are correct. The filter is completely useless if it is filled with 1s. In this situation, you would just use a larger filter. I am not sure exactly what the ideal size is, it depends on the desired probability of false positives, but an optimally large filter for the data you are using will have some empty bits.
- bane 9y ago
  Here's a helpful calculator, it will even tell you the optimal number of hash functions. All you have to know is the expected cardinality of the set. https://hur.st/bloomfilter https://hur.st/bloomfilter
  - afonsotsukamoto 9y ago
    ah! ok - I just had a "mind bending" moment after looking at the calculator + tekromancr's response. I thought we would want to control the number of hash functions (k) and the number of items (n) but I guess the most common use case will be to set the allowed probability of a false positive for the number of allowed items and let the "system" control the k and m (hash functions and bits in the filter) Enlightening! One question remains though - since the number of bits (m) is a function of the probability of false positives (p) and the number of hash functions (k) is a function of the number of bits and the number of items (n), does it mean that once we start a bloom filter we can't update the number of items or the desired probability of false positives? My assumption is that if we change p, then m will change, which would make the k functions "obsolete" as they're being "mapped" to a new sized m. Same for n, which would change the k functions, making it so that a new item would be hashed differently, making m hits/misses obsolete again. Might be missing something here though. Either way, I still find bloom filters a fascinating data structure.
    - tekromancr 9y ago
      Nope, I think you got it. My understanding is that if you want to change the params, you need to rebuild the filter.