A visual interactive guide to Bloom filters

Sam&#x27;s visual tutorials are as good as ever (doggos are very important, by the way).<p>And if you want to try some code, I&#x27;ve prepared three toy Bloom filter implementations to accompany the article:<p>JavaScript: <a href="https:&#x2F;&#x2F;codapi.org&#x2F;embed&#x2F;?engine=browser&amp;sandbox=javascript&amp;src=gist:e7bde93f98c5e47ca38d359a5104fd88:bloom.js" rel="nofollow">https:&#x2F;&#x2F;codapi.org&#x2F;embed&#x2F;?engine=browser&amp;sandbox=javascript&amp;...</a><p>Python: <a href="https:&#x2F;&#x2F;codapi.org&#x2F;embed&#x2F;?sandbox=python&amp;src=gist:e7bde93f98c5e47ca38d359a5104fd88:bloom.py" rel="nofollow">https:&#x2F;&#x2F;codapi.org&#x2F;embed&#x2F;?sandbox=python&amp;src=gist:e7bde93f98...</a><p>Go: <a href="https:&#x2F;&#x2F;codapi.org&#x2F;embed&#x2F;?sandbox=go&amp;src=gist:e7bde93f98c5e47ca38d359a5104fd88:bloom.go" rel="nofollow">https:&#x2F;&#x2F;codapi.org&#x2F;embed&#x2F;?sandbox=go&amp;src=gist:e7bde93f98c5e4...</a>

I&#x27;m the author of this post, and am happy to answer any questions. :)

Thanks to the author for all the hard work. Its easy to consume and understand for beginners too.

I remember discussing bloom and cuckoo filters a while back and someone linked.to.great papers from late 2010s with much more advanced probabilistic structures that were handling modification much better or had other interesting properties. Anyone here knows where to look for these? I didn&#x27;t take notes...

What are the business use cases we use bloom filters? Some examples would be great. Thanks!

A wonderful article, thank you.<p>Rather than using multiple hash functions, would it make more sense to use a single algorithm over (prefix | input), with k different prefixes? This may allow computing those hashes in parallel, using SIMD for example, and caching the prehash state of the prefixes.<p>Edit: looks like there has been some research on this: <a href="https:&#x2F;&#x2F;ieeexplore.ieee.org&#x2F;document&#x2F;8462781" rel="nofollow">https:&#x2F;&#x2F;ieeexplore.ieee.org&#x2F;document&#x2F;8462781</a>

this is a great article! I love how you explained it. here are my takeaways from it: - Bloom filter is a space-efficient data structure - You&#x27;re trading off some accuracy (possibility of false positives) for the significantly smaller memory footprint and faster membership checks

Very good explanation of Bloom filters, but are they optimum from a complexity point of view given a false positive rate and a bounded number of bits? Are there other kind of filters if we relax de condición of zero false negative rate?, are there other better but more complex data structures able to provide the same effect?

For whom that are interested I suggest also to have a look on Cukoo Filter: <a href="https:&#x2F;&#x2F;www.cs.cmu.edu&#x2F;~dga&#x2F;papers&#x2F;cuckoo-conext2014.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.cmu.edu&#x2F;~dga&#x2F;papers&#x2F;cuckoo-conext2014.pdf</a>

I appreciate the author&#x27;s dedication to making animations accessible!

These are beautiful interactives along with the rest by Sam!

Awesome resource! Bloom filters are one of my favorite data structure (that I wish I got to employ more often in my line of work… but alas).

Very cool! I was going to read up on bloom filters and this popped up the next day!

Amazing! Very well explained.

Flows beautifully. Looking forward to the next one Sam!

Would it be better to store the hash of each output into 3 different arrays?<p>e.g. currently, it&#x27;s doing:<p><pre><code> [input] -&gt; [3 hashes] -&gt; [single storage] </code></pre> but, I&#x27;m wondering if it&#x27;s better to do:<p><pre><code> [input] -&gt; [hash a] -&gt; [storage a] -&gt; [hash b] -&gt; [storage b] -&gt; [hash c] -&gt; [storage c] </code></pre> ...this way, the output of the 3 hashes don&#x27;t affect each other during the set and membership-check. I wonder how that would affect how much more data you can store. I&#x27;m sure someone has considered this.

very well written and informative.