11–20 of 56 posts
obligatory mention that if you are interested in this you should also know about cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://en.wikipedia.org/wiki/Cuckoo_hashing
Do you have a tldr for how/when it is better than bloom filters?
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: https://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.
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?).
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: https://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.
hey, curious why your variables in the go version are so terse? makes following along a little tough!
The abstractions are supposed to be self explanatory and simple and thus the variable names do not have to serve as documentation.
obligatory mention that if you are interested in this you should also know about cuckoo filters: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://en.wikipedia.org/wiki/Cuckoo_hashing
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…
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.
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.
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 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.