To be complete something along the lines of: ‘if the answer is “maybe yes” a more computationally expensive is used to definitely decide yes or no’ should me added imo
Bloom filters explained in a single image
21–30 of 50 posts
Re: Bloom filters explained in a single image
#22What is it about bloom filters that makes people want to explain them to others? I think I’ve seen more blog posts about them than any other cs topic, with the possible exception of monads.
Because despite all the posts a lot of people still don’t get how they work.
I did a brown bag where I work recently when I walked though how to implement one and was approached after by some of the smartest engineers I know saying thank you I think I finally get it.
Re: Bloom filters explained in a single image
#23Earlier quoted context omitted.
Hi, author here! I think you're absolutely right. In my case, I found them a beautiful data structure that is simple to understand but very useful. I also draw the images for learning myself about a topic, maybe others find the format useful, so I have started sharing them. But yes, I have definitely planned to draw/explain other data structures and computer science concepts. I did bloom filters now because I'm explo…
Hi there! Not a criticism, I appreciate that you are putting out educational content. Rather, it was a genuine question. If you’re exploring cryptography, I highly recommend looking into Shamir’s secret sharing algorithm. It’s very elegant and doesn’t require much in the way of higher math to understand.
Thanks for the suggestion! I had never heard about it, but like you said, it looks like an elegant, "simple" and useful algorithm. I'll definitely look into it!
Re: Bloom filters explained in a single image
#24What is it about bloom filters that makes people want to explain them to others? I think I’ve seen more blog posts about them than any other cs topic, with the possible exception of monads.
If they were called Leaky HashSets/ leaky dictionaries i don't think it would be as popular. Monads and bloom filters both have names that don't help the meaning.
Re: Bloom filters explained in a single image
#25Hi, author here! I have created that site to summarize concepts I find interesting, while providing examples or use cases. My biggest inspiration comes from Julia Evans and her zines[0]. I started drawing the things I was learning about, and I thought the format could be useful for other people. Right now I'm diving into a mix of hashing functions/cryptography, data structures and databases. I usually spend a few day…
Evans is an absolute gem, and I'm delighted to see their influence on others. Thank you for trying to help others, it's always refreshing.
Re: Bloom filters explained in a single image
#26thanks for the post, it inspired this naive code:
class BloomFilter:
def __init__(self, size):
self.f = [0] * size
def contains(self, s):
h1, h2, h3 = self.hashes(s)
if self.f[h1] * self.f[h2] * self.f[h3] == 1:
return 'Value might be in the set.'
else:
return 'Value is definitely not in the set.'
def hashes(self, s):
h1 = hash(s) % len(self.f)
h2 = hash(s + 'salt') % len(self.f)
h3 = hash(s + 'more salt') % len(self.f)
return h1, h2, h3
def insert(self, s):
h1, h2, h3 = self.hashes(s)
self.f[h1] = self.f[h2] = self.f[h3] = 1
bf = BloomFilter(64)
bf.insert('bill')
print(f"{bf.contains('bill') = }")
print(f"{bf.contains('bob') = }")
Out:
bf.contains('bill') = 'Value might be in the set.'
bf.contains('bob') = 'Value is definitely not in the set.'Re: Bloom filters explained in a single image
#27Earlier quoted context omitted.
Hi, author here! I think you're absolutely right. In my case, I found them a beautiful data structure that is simple to understand but very useful. I also draw the images for learning myself about a topic, maybe others find the format useful, so I have started sharing them. But yes, I have definitely planned to draw/explain other data structures and computer science concepts. I did bloom filters now because I'm explo…
Hi there! Not a criticism, I appreciate that you are putting out educational content. Rather, it was a genuine question. If you’re exploring cryptography, I highly recommend looking into Shamir’s secret sharing algorithm. It’s very elegant and doesn’t require much in the way of higher math to understand.
https://github.com/codahale/shamir
A beautiful Beautiful algorithm
Re: Bloom filters explained in a single image
#28Bloom filters explained in a single HN comment:
They are an efficient implementation of a Set that contains hashes of the elements.
bloomfilter.add("foo") will internally add hash("foo") to the Set
bloomfilter.has("foo") checks if the Set contains hash("foo")
False positives arise due to different elements hashing to the same hash. If "foo" and "bar" hash to the same value, bloomfilter.has("bar") would return true.
No false negatives are possible.
They are used when an actual check for an element in a datastructure is quite costly and the hitrate for not-in-the-datastructure is non-trivial and can therefor be skipped if the bloomfilter gives a negative.
Re: Bloom filters explained in a single image
#29I've used Bloom filters and found them to be memory latency bound, as queries can not be cached (big data structure, random access). Any recommendations on how to speed up queries?
Re: Bloom filters explained in a single image
#30I've used Bloom filters and found them to be memory latency bound, as queries can not be cached (big data structure, random access). Any recommendations on how to speed up queries?
1) Don't access randomly. That means either that the hash function you use is more like a reducing/mapping function (i.e. order preserving), or you iterate in the hashed order of your data. Obviously, this only works for scans and batch processes, not random user queries unless you can batch them.
2) Have a leakier bloom that fits in your L1/L2 cache size. You may have to have 2 layers of bloom filters, and this will be highly dependent on the relative expenses of the various operations.