Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bloom filters explained in a single image

exampl.io

Post reply on HN
Print view View original

31–40 of 50 posts

Re: Bloom filters explained in a single image

#31

Post by polyrand »

reivalc wrote: post #26

thanks 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…

This looks fantastic! I also implemented one from scratch[0], and I was doing something very similar at first. Then I found the Python hash() function returns different outputs for the same input when you restart the interpreter. I really like your implementation, it's functional and easy to understand!

[0] https://ricardoanderegg.com/posts/understanding-bloom-filter...

Re: Bloom filters explained in a single image

#32

Post by PUSH_AX »

eis wrote: post #28

Bloom 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. N…

This was easier to digest than the "image". Thanks.

Re: Bloom filters explained in a single image

#33

Post by mimimi31 »

tonke90 wrote: post #29

I'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?

You could use Blocked Bloom Filters[1]. It's essentially many small Bloom Filters that each fit into a cache-line. The first hash function decides, which of the smaller Bloom Filters an element will be saved in and can still cause a cache miss. All subsequent accesses to the small Bloom Filters are cached.

The main drawback is that, because the elements won't be completely evenly distributed among the small Bloom Filters, you need some additional space to compensate and keep the false positive rate low.

[1] https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic...

Re: Bloom filters explained in a single image

#34

Post by polyrand »

eis wrote: post #28

Bloom 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. N…

Thanks for your comment! (I'm the author of the image/poster). At first, I wanted to give a similar explanation than yours, but then decided to make it more verbose / less technical, and it ended up having more text that I would like to.

Also, your last sentence is a great summary of when they should be used. I included a few use cases, but I should have also included something like what you said.

I'll take that into account for future posts, thanks!

Re: Bloom filters explained in a single image

#37

Post by einpoklum »

bradleyjg wrote: post #10

What 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.

Maybe the fact that they seem to be massively under-utilized, compared to hash tables? Despite being not much more complicated than hash tables?

Also, you don't seem to have them available in popular container or general-purpose libraries.

Re: Bloom filters explained in a single image

#38

Post by joshlemer »

llaolleh wrote: post #12
bradleyjg wrote: post #10

What 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.

That was what was going through my mind too! What makes it so fascinating compared to other beautiful structures?

What other beautiful structures come to mind for you?

Re: Bloom filters explained in a single image

#39

Post by joshlemer »

bryzaguy wrote: post #36

Can someone help me understand the value of hashing? If you’re using modulus to bucket, why not just use the string length or something? Is it because the values will distribute across buckets more uniformly?

Yes that's exactly right. Taking the length of a string could be considered a hash function, it's just a very poor one.
Post reply on HN