4 ms·

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

stevenguh 5y ago
Try watching this video: https://youtu.be/Bay3X9PAX5k https://youtu.be/Bay3X9PAX5k
avinassh 5y ago
try this? - https://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/
kenniskrag 5y ago
or this of a student: https://elsensohn.ch/en/docs/distributed-systems/bloom-filter/ https://elsensohn.ch/en/docs/distributed-systems/bloom-filte...
rattlesnakedave 5y ago
You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken. So what you can do is make a bloom filter, which is basically just an array of bits of n length. Let’s say 10 for our example. Then gather some hash functions (h1, h2, and h3). When someone inputs a username, you run it through the hash functions, and modulo by the number of bits, and get an integer result. So: h1(“rattlesnakedave”) % 10 = 3 h2(“rattlesnakedave”) % 10 = 7 h3(“rattlesnakedave”) % 10 = 2 Then you check the bits at position 3,2, and 7 in the array. If they any of the bits are set to 0, we haven’t seen the username before. If they’re all set to 1, we have possibly seen the username before. Let’s say they’re all set to 0, so we probably haven’t seen it. We can present the message that the username is available, and allow registration. During registration, we can do a slower more expensive verification that the username isn’t actually in the dataset. Now that the username is in the dataset, we can flip the bits on our bloom filter at position 3,2, and 7 to 1. So the next time we lookup that username we can tell quickly that it’s probably taken. There is no way to delete from the bloom filter. The more values you store relative to its size, the more false positives you get. Hopefully that makes sense, and is correct.
- Taywee 5y ago
  Not exactly correct. If all of the bits is 1, then the value is possibly in the set (not "probably", but "possibly", with the likelihood being affected by the sizes of the set and the array). If any of the bits is zero, the value definitely isn't in the set (also not "probably haven't", but definitely not).
  - rattlesnakedave 5y ago
    Good catch! Thank you. Was trying to keep the initial explanation simple by leaving out the false positives scaling relative to the size of the array and set, and then clarifying at the end. The second part (any 0 bits it hasn’t been seen) is true, a goof up on my part.
- DougBTX 5y ago
  Usernames is a nice example. Just as a demo, we could make things simpler: Look at all the usernames in the input, keep track of all the letters you’ve seen. When you get a new name, if you’ve seen all the letters before, you might have seen the name before. If there’s a new letter, it must be a new name. Obviously that isn’t a great hash function, some letters are more common than others, so real Bloom filters use better ones, but it works basically the same way.
a11r 5y ago
The original paper by Burton H. Bloom is only 5 pages and very readable. https://dl.acm.org/doi/10.1145/362686.362692 https://dl.acm.org/doi/10.1145/362686.362692
- ghostly_s 5y ago
  https://sci-hub.st/https://doi.org/10.1145/362686.362692 https://sci-hub.st/https://doi.org/10.1145/362686.362692
6510 5y ago
let me butcher the concept for you :) say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that this name is not in the data set. If "jack" reduces to 1 and we look him up we see 1 is set so this name *might be* there.
- cma 5y ago
  Isn't this just similar to hash prefixes and not a true bloom filter?
  - 6510 5y ago
    I did say I'd butcher it. :-) imho one shouldn't be overly attached to an exact implementation but learn to reason about it. You could for example make an array and count how many times each bit was set. A textbook bloomfilter doesn't allow you to remove things but if you count how often a bit was set you obviously can.
dr_kiszonka 5y ago
I will take an imposter over a grandiose narcissist any day! (But then I am an imposter too.)
- robertlagrant 5y ago
  > If everyone is am imposter, no one is! - Syndrome
actually_a_dog 5y ago
This article has a pretty good explanation, IMO: https://freecontent.manning.com/all-about-bloom-filters/ https://freecontent.manning.com/all-about-bloom-filters/
taeric 5y ago
I always think of them as "bouncer filter." Think of them as asking a bouncer if they have seen a suspect enter a club. They don't know folks by name, but can answer a series questions about the people that entered. Then, the "hashes" are effectively your new questions. Did someone with green hair enter? Did someone limping enter? Wearing a hat? Etc To that end, it is clear that you won't get a definitive yes to entry. You may get a sufficient no, though.
GVRV 5y ago
They finally clicked for me after reading about how they're used by the bitcoin network: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch08.asciidoc#bloom-filters https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch08...

stevenguh 5y ago

Try watching this video: https://youtu.be/Bay3X9PAX5k https://youtu.be/Bay3X9PAX5k

avinassh 5y ago

try this? - https://llimllib.github.io/bloomfilter-tutorial/ https://llimllib.github.io/bloomfilter-tutorial/

kenniskrag 5y ago

or this of a student: https://elsensohn.ch/en/docs/distributed-systems/bloom-filter/ https://elsensohn.ch/en/docs/distributed-systems/bloom-filte...

rattlesnakedave 5y ago

You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken. So what you can do is make a bloom filter, which is basically just an array of bits of n length. Let’s say 10 for our example. Then gather some hash functions (h1, h2, and h3). When someone inputs a username, you run it through the hash functions, and modulo by the number of bits, and get an integer result. So: h1(“rattlesnakedave”) % 10 = 3 h2(“rattlesnakedave”) % 10 = 7 h3(“rattlesnakedave”) % 10 = 2 Then you check the bits at position 3,2, and 7 in the array. If they any of the bits are set to 0, we haven’t seen the username before. If they’re all set to 1, we have possibly seen the username before. Let’s say they’re all set to 0, so we probably haven’t seen it. We can present the message that the username is available, and allow registration. During registration, we can do a slower more expensive verification that the username isn’t actually in the dataset. Now that the username is in the dataset, we can flip the bits on our bloom filter at position 3,2, and 7 to 1. So the next time we lookup that username we can tell quickly that it’s probably taken. There is no way to delete from the bloom filter. The more values you store relative to its size, the more false positives you get. Hopefully that makes sense, and is correct.

Taywee 5y ago
Not exactly correct. If all of the bits is 1, then the value is possibly in the set (not "probably", but "possibly", with the likelihood being affected by the sizes of the set and the array). If any of the bits is zero, the value definitely isn't in the set (also not "probably haven't", but definitely not).
- rattlesnakedave 5y ago
  Good catch! Thank you. Was trying to keep the initial explanation simple by leaving out the false positives scaling relative to the size of the array and set, and then clarifying at the end. The second part (any 0 bits it hasn’t been seen) is true, a goof up on my part.
DougBTX 5y ago
Usernames is a nice example. Just as a demo, we could make things simpler: Look at all the usernames in the input, keep track of all the letters you’ve seen. When you get a new name, if you’ve seen all the letters before, you might have seen the name before. If there’s a new letter, it must be a new name. Obviously that isn’t a great hash function, some letters are more common than others, so real Bloom filters use better ones, but it works basically the same way.

a11r 5y ago

The original paper by Burton H. Bloom is only 5 pages and very readable. https://dl.acm.org/doi/10.1145/362686.362692 https://dl.acm.org/doi/10.1145/362686.362692

ghostly_s 5y ago
https://sci-hub.st/https://doi.org/10.1145/362686.362692 https://sci-hub.st/https://doi.org/10.1145/362686.362692

6510 5y ago

let me butcher the concept for you :) say though nummerology you reduce the character values of a name to a number 0-10. Lots of names will reduce to the same number. We take 11 bits and for "jim" we set the first bit. We have only one name in our data set so all other bits are 0. Now if someone types "joe" in the search box and it reduces to 2 we look at the second bit, see it is a zero and know 100% *for sure* that this name is not in the data set. If "jack" reduces to 1 and we look him up we see 1 is set so this name *might be* there.

cma 5y ago
Isn't this just similar to hash prefixes and not a true bloom filter?
- 6510 5y ago
  I did say I'd butcher it. :-) imho one shouldn't be overly attached to an exact implementation but learn to reason about it. You could for example make an array and count how many times each bit was set. A textbook bloomfilter doesn't allow you to remove things but if you count how often a bit was set you obviously can.

dr_kiszonka 5y ago

I will take an imposter over a grandiose narcissist any day! (But then I am an imposter too.)

robertlagrant 5y ago
> If everyone is am imposter, no one is! - Syndrome

actually_a_dog 5y ago

This article has a pretty good explanation, IMO: https://freecontent.manning.com/all-about-bloom-filters/ https://freecontent.manning.com/all-about-bloom-filters/

taeric 5y ago

I always think of them as "bouncer filter." Think of them as asking a bouncer if they have seen a suspect enter a club. They don't know folks by name, but can answer a series questions about the people that entered. Then, the "hashes" are effectively your new questions. Did someone with green hair enter? Did someone limping enter? Wearing a hat? Etc To that end, it is clear that you won't get a definitive yes to entry. You may get a sufficient no, though.

GVRV 5y ago

They finally clicked for me after reading about how they're used by the bitcoin network: https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch08.asciidoc#bloom-filters https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch08...