If you're interested in using Bloom filters in the backend, we (at DCSO) have written efficient and interoperable open-source implementations in Python and Go, also using FNV-1 hashing:
I think it is Go style to name things that come in as interfaces with short names. When you have an io.Writer, there's very little else you can name it other than "w" that would have any additional meaning or utility. When you have a variable or struct field of a concrete type, it can and should have a meaningful name, even in Go.
Ironically, I see several "input io.Reader" sort of things in that code, where as "number of hash functions" is k. A few minutes with go-rename would clean that right up, though.
One note: if you've done everything correctly under the hood, instead of reading and writing the entire filter into and out of memory, just mmap the file and operate on it directly. It turns out to be pretty fast, especially on SSDs and you can make both many filters and test them quickly this way, or make filters that are practically larger than RAM and swap partitions and make absolutely enormous sets.
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?).
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.
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
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.
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.
For this toy example, sure. But extend it from a 2byte table to, for example, a 50MB table and use many more hashes. The larger the table, and the more hash functions you use, the smaller the false positive error becomes. If you have a limited dataset that you want to test against, you can set these params to have a near 0% false positive rate, at the expense of a much larger table
If you want a simple explanation of bloom filters:
To add to filter:
1) Get multiple hashes of the data. You can use the same hash function and increment the data each hash, or use multiple hash functions. You can do any amount of hashes from 1 to infinity, each filter size and dataset size has a sweet spot.
2) Mod (remainder) each hash by the filter size. The filter size can be any size, 1 to the maximum hash from your function[s]. The larger the filter, the more accurate the results, but a filter larger than your dataset is obviously useless.
3) Set each bit at the locations (from step 2) in the filter to 1.
To check filter:
1) Do steps 1 & 2 from previous procedure.
2) Check each location in the filter. If all locations are 1, the data might be in the filter. If any of the locations are 0, the data is definitely not in the filter.
Well,the bloom filter only uses a tiny bit of space per data element and doesn't actually store the data. When searching the data itself, you're often searching through the actual data, which is more intensive and slow.
I think CS education would be improved if these concepts didn't have mysterious names.
Respect to Bloom, but the programming median might be raised if Bloom filters were called something stupid obvious like Hash Array Filler-upper Tables. We might not even need to spend time making visualizations to explain them.
I have no idea why you think the name helps remove the need for a visualization. Besides I think "filter" is more apt than "table"—it doesn't store anything per se.
I never needed a picture to understand a hash table once I knew what a hash function was. If it were called a McCready table, that's one more trip to Wikipedia, plus one more every time I forget.
Re: naming: It's a table of hash function results. It probabilistically stores a set. I don't see any filter here, though one use of the technique is indeed in filtering a list, though there are plenty more.
Right, but you're describing the implementation, which doesn't imply anything about its use. I prefer to name by the latter: the implemenation is just a detail on how the filter does its filtering.
Those who already know what a Bloom Filter is would probably the find the name more convenient than having to say a short description every time. Those that are just learning programming might argue that Hash, Array, Boolean, String, etc. would be understood faster if they had more descriptive names.
Having a short, distinctive name helps in differentiating and reasoning about the different objects. Think of an everyday programming-related discusion that includes hashes, arrays, and strings, and think about making the following substitutions:
- Hash : Contiguous Allocation with Well-Shuffled Value-Derived Indexes
- Array : Contiguous Allocation of Same Typed Values
- String : Contiguous Allocation of Character Values
Last time this came up, I gave my wish that these had been called something like a Concierge filter. The metaphor being that you can ask the concierge of a hotel several questions about people that have been seen entering to get an idea if a given person is probably there.
While I'm not sure I agree about mysterious names, I do get confused whenever Bloom filters are mentioned on HN. I always think they're about bloom filters as applied to computer graphics:
Bloom filters are O(1), but are probabilistic. So they're faster than even an indexed lookup in a database... but they don't always give you the correct answer.
They are also helpful in terms of space savings. I worked at a startup in Palo Alto in 2011 where we used a 100 GB in memory (Redis) Bloom Filter to de-duplcate links coming in from a real-time social media stream (Facebook, Twitter, Forums, etc..). While Bloom Filter does introduce false positives (collisions) we were willing to take the bet on that rather than allowing duplicate social media posts in our pipeline.
If we wanted to store this information in a regular hash table, we would require a lot more space than the 1 bit per entry of a Bloom Filter.
55 comments
[ 3.4 ms ] story [ 104 ms ] threadhttps://github.com/DCSO/bloom (Go version)
https://github.com/DCSO/flor (Python version)
The Go version comes with a command line tool that allows you to use Bloom filters on the shell.
The abstractions are supposed to be self explanatory and simple and thus the variable names do not have to serve as documentation.
Ironically, I see several "input io.Reader" sort of things in that code, where as "number of hash functions" is k. A few minutes with go-rename would clean that right up, though.
Go to https://golang.org/pkg/net/http/#Client and use your browser to search for the string "struct {" and have a look. https://golang.org/pkg/os/ is another page with a number of struct declarations.
But that's a new hash function then.
https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
https://en.wikipedia.org/wiki/Cuckoo_hashing
https://github.com/kristoff-it/redis-cuckoofilter
This could be a good use case for WebAssembly, which supports 64-bit math natively.
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?).
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.
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
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.
https://hur.st/bloomfilter
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.
To add to filter:
1) Get multiple hashes of the data. You can use the same hash function and increment the data each hash, or use multiple hash functions. You can do any amount of hashes from 1 to infinity, each filter size and dataset size has a sweet spot.
2) Mod (remainder) each hash by the filter size. The filter size can be any size, 1 to the maximum hash from your function[s]. The larger the filter, the more accurate the results, but a filter larger than your dataset is obviously useless.
3) Set each bit at the locations (from step 2) in the filter to 1.
To check filter:
1) Do steps 1 & 2 from previous procedure.
2) Check each location in the filter. If all locations are 1, the data might be in the filter. If any of the locations are 0, the data is definitely not in the filter.
This isn't obvious to me, can you explain?
Respect to Bloom, but the programming median might be raised if Bloom filters were called something stupid obvious like Hash Array Filler-upper Tables. We might not even need to spend time making visualizations to explain them.
Re: naming: It's a table of hash function results. It probabilistically stores a set. I don't see any filter here, though one use of the technique is indeed in filtering a list, though there are plenty more.
... this naming stuff it hard
Those who already know what a Bloom Filter is would probably the find the name more convenient than having to say a short description every time. Those that are just learning programming might argue that Hash, Array, Boolean, String, etc. would be understood faster if they had more descriptive names.
Having a short, distinctive name helps in differentiating and reasoning about the different objects. Think of an everyday programming-related discusion that includes hashes, arrays, and strings, and think about making the following substitutions:
- Hash : Contiguous Allocation with Well-Shuffled Value-Derived Indexes
- Array : Contiguous Allocation of Same Typed Values
- String : Contiguous Allocation of Character Values
- Boolean : Either True or False Value
https://en.wikipedia.org/wiki/Bloom_(shader_effect)
If we wanted to store this information in a regular hash table, we would require a lot more space than the 1 bit per entry of a Bloom Filter.