4 ms·
Am I understanding this correctly? 1) For each key, you generate a "hash" - which is a bit position 2) The hash generation is such to ensure that the bit loca
by cr0sh 9y ago
Am I understanding this correctly?
1) For each key, you generate a "hash" - which is a bit position
2) The hash generation is such to ensure that the bit location in the filter is probabilistically distributed for each key (so they are spread "evenly", for lack of a better term, over the length of the filter)
3) You generate so many locations per key, the number of which is the number of hash generators you are using (so if you have 3 generators, you get 3 distributed bit positions)
4) Some keys may cause overlaps/collisions - but this is ok
5) At some point, you fill up the filter with keys
6) To see if a key is -probably- in the filter, you run the same steps again and see if the bits are set; if they are, then it -probably- is
7) You then run that key on your regular index search; some false positives though will cause you to run that expensive operation and get back nothing, but usually you'll get back something (true positive). But if that key wasn't found in the filter, you definitely don't run the expensive lookup at all.
Is that correct?
There must also be something that the bit position "hash" generators have to be able to span an arbitrarily large bit range, in order to "store" more keys; this trivial example would look like it would fill up rather quickly (one all bits are set to "1", any key would generate a "positive" and you would always be running the expensive lookup - whether it was in the index or not - basically, falling back to a default state).
If I have all of that correct (or close) - or even if I don't - it seems like a very powerful technique, limited to only that bit length (and being able to perform bitwise operations on it quickly), which (unless I am missing something?) would need to be fairly long to accommodate a reasonable number of keys (for say a record lookup in an rdb table).
What might also be nice would be a way to detect it is "filled up" and bypass the test; you'd fall back to the worst case scenario (ie - no bloom filter), but at least you wouldn't be running the bloom filter check on top of that as well, incurring an extra demand. I'm thinking there's probably something easily done here - some bitwise operation that could be done (maybe take the inverse and compare it to zero?).
- tekromancr 9y agoPretty 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 agoI 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 agoYou 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 agoHere'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 agoah! 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.