Bloom filters explained in a single image | Hacker News Reader

Bloom filters explained in a single image

exampl.io

98 pointspolyrand48 comments

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.

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.

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!

I don't think that's quite right though. A bloom filter does not keep a list of hashes. If it did it'd grow with every item added to the set, and it doesn't. A bloom filter adds a new hash by bitwise-or-ing it with the currently stored value. Checking if a hash is present in the bloom filter is as simple as checking that all the 1 bits in the bash are 1 bits in the stored value in the bloom filter. This makes sure there are never any false negatives because bits only ever get turned on, never off. False positives are possible because of either direct hash collisions, or unrelated hashes turning on enough bits for a match.

It's indeed not a list of hashes but (as I said) a set of hashes. Usuaully the size of the set is static and determined when creating the bloom filter (how many bits in the bitmap). The hashes are not full blown hashes like a sha1 sum or similar but a bit (or a few) in the bitmap. You only add to the set and never remove. The bitwise or-ing with the stored value is the mentioned hash collision and just an implementation detail. It's still a set of hashes.

"unrelated hashes turning on enough bits for a match" is the case of hash collisions or I am misunderstanding that part.

So it means with a dataset big enough, your bloom filter is virtualy all 1s, and will return true for every values you want to check regardless if it is actually in there ? Is there a threshold you can monitor to avoid this situation ?

Yes, if a dataset keeps growing, the whole bloom filter will eventually become 1s. If you know the (approximate) expected size of your dataset and the probabilities of false positives you can tolerate, you can calculate how big the filter should be and how many hashing functions you have to use.

I guess there are other techniques to dynamically grow the filter when you need it.

I think this is a great explanation for using a bloom filter and getting a feel for why you can get false positives but not false negatives.

Super useful and succinct!

This explanation could apply to a few hash-set style implimentations but I think it misses what made the bloom filter so beautiful and elegant when I'd discovered it. It's a specific data structure with it's own memory/performance/tuning profiles!

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

"bloom filters explain in a single image" where 90% of the image is text. so just bloom filters explained in 2-3 paragraphs?

fig 3 here

https://www.sciencedirect.com/science/article/pii/S138912861...

is a much better "single image" explanation (insofar as any single image could be sufficiently explanatory) of bloom filters.

Fulltext and figures of that paywalled journal article available here:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.428...

ah thanks i didn't realize i had my institutional account logged in

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.

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 exploring concepts related to hashing and cryptography.

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!

https://github.com/codahale/shamir

A beautiful Beautiful algorithm

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.

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.

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

They are easy to explain.

What other beautiful structures come to mind for you?

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.

Hi, 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 days learning about a concept, and then I try to summarize it in a constrained drawing frame (I use Excalidraw[1] to do it and some logos from drwn.io[2]). I'm happy to accept suggestions about interesting topics to explore, draw and summarize.

[0] https://wizardzines.com/ [1] https://excalidraw.com/ [2] https://drwn.io/

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.

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

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

Nice!

> found the Python hash() function returns different outputs for the same input when you restart the interpreter

I wasn't aware of this >>

This is great but the title is a little misleading for me. Perhaps "bloom filters explained in a poster"...

This contains multiple paragraphs and figures. You couldn't screenshot a wikipedia page and claim the same!

I didn't understand a thing from this image but I was definitely intrigued and so I found a video on Youtube(1) that explains it quite simply (like for dummies) and now I fully understand it!

You can watch it at 2.5x speed without missing out on anything:

https://www.youtube.com/watch?v=kfFacplFY4Y

Yes thanks, also 2.5x is not supported by youtube, so i use https://chrome.google.com/webstore/detail/youtube-playback-s...

For a really high level that includes how people practically use one with storage, I like this simple image:

https://academy.bit2me.com/wp-content/uploads/2020/06/como-f...

Fun fact: the original pre-computer punch cards used for the census etc. were quite like Bloom filters with degenerate hash functions. Some of the same principles of key number/width, density, and pollution even apply. I've often thought that would be a good place to start, if I ever had to explain Bloom filters to a layman or beginner.

I've just thought about how you could also have a "Bloom Map", basically as a HashSet is to Bloom Filter, a HashMap would be to a Bloom Map. It would be able to answer lookups with either "Definitely not present" or "Might map to value XYZ".

A use of the bloom filter is to determine whether you need to make an expensive call to storage to check for a match. You use a smaller fraction of memory to avoid 99 out of 100 disk accesses than you would to have a full index of the data.

My first thought about Bloom filters is always what does this have to do with shaders.

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.

> Bloom filters test if an element is part of a set, without needing to store the entire set

https://python.land/bloom-filter

There.

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

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.

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

Can this be explained, more simply, by saying that many different strings will be represented by a single hash?

I think of them as Hashtables minus collision handling.

I don't think so because that is a property of hash-maps, rather it seems to test some properties of an item to know that it is not in the set or that it might be in the set

What's the intuition behind the name?

> “A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970,”

https://en.wikipedia.org/wiki/Bloom_filter

Ah, thanks haha.

Reply on news.ycombinator.com