4 ms·

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

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.

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.