<story><title>Bloom Filters by Example (2013)</title><url>https://llimllib.github.io/bloomfilter-tutorial/</url></story><parent_chain><item><author>tosh</author><text>Does anyone have interesting examples for when a bloom filter came in handy as a solution to a problem?&lt;p&gt;I would love to have some (more than the contrived standard) examples to draw upon to make it easier for me to intuitively notice that a bloom filter might be a good fit in a future problem I encounter.</text></item></parent_chain><comment><author>cmurphycode</author><text>In deduplication, we check to see whether a block has been seen before. If it has, we don&amp;#x27;t write it. If it hasn&amp;#x27;t, we write it down and record that information for next time. Checking if a block has been seen requires looking in an index, which is large and expensive to check, but recording the store can be amortized.&lt;p&gt;So, a bloom filter can tell you whether it&amp;#x27;s worth spending the expensive check to verify that the block is a duplicate, or whether you should skip that behavior and move on directly.&lt;p&gt;Same is true for malicious site detection. Google offers this feature in Chrome, but we don&amp;#x27;t want to make an expensive network request for every URL we visit. And we can&amp;#x27;t really have a database of all malicious URLs downloaded and updated to everyone&amp;#x27;s computer. Instead, they can distribute a bloom filter of malicious sites. if the bloom filter says it&amp;#x27;s malicious, we can afford to check the network for the final answer. If the bloom filter says it&amp;#x27;s not, we know we don&amp;#x27;t have to check (and that&amp;#x27;s the most common case, too!)&lt;p&gt;In my opinion, the intuition to extract is this. If you need to check membership, the set is expensive to check, and getting a definitive NO is valuable, then you can consider a bloom filter (or another probabilistic structure like a cuckoo filter).
In dedup, we need to check membership, the index is big enough to not fit in RAM so it&amp;#x27;s expensive, and getting a definitive NO means we can skip the index check. 
In malicious site detection, we need to check membership, the answer requires a network round trip so it&amp;#x27;s expensive, and getting a definitive NO means we can just move on to loading the site.</text></comment>
<story><title>Bloom Filters by Example (2013)</title><url>https://llimllib.github.io/bloomfilter-tutorial/</url></story><parent_chain><item><author>tosh</author><text>Does anyone have interesting examples for when a bloom filter came in handy as a solution to a problem?&lt;p&gt;I would love to have some (more than the contrived standard) examples to draw upon to make it easier for me to intuitively notice that a bloom filter might be a good fit in a future problem I encounter.</text></item></parent_chain><comment><author>shereadsthenews</author><text>Schachter and Ceglowski’s &amp;quot;LOAF&amp;quot;, or List of all Friends, was a way to distribute a random projection of your email contacts publicly and anonymously.  It was based on Bloom filters and actually I learned of Bloom filters by hearing Schachter&amp;#x27;s talk on LOAF at Eyebeam long ago. Basically you distribute the projection in an email header or signature and the recipient can probe it to see if they might have any contacts in common.</text></comment>