Show HN: BoomFilters – Probabilistic data structures for processing streams

<i>&#x2F;&#x2F; The InverseBloomFilter may report a false negative but can never report a false positive.</i><p>This is actually not true and not possible. There is a good explanation here: <a href="http:&#x2F;&#x2F;cstheory.stackexchange.com&#x2F;a&#x2F;14455&#x2F;43" rel="nofollow">http:&#x2F;&#x2F;cstheory.stackexchange.com&#x2F;a&#x2F;14455&#x2F;43</a><p>There will be a low probability of false positives ~ 2^32*k. (Also it&#x27;s not an inverse-bloom filter, it&#x27;s a cache).

That InverseBloomFilter sounds like an LRU cache of hashes. A true inverse bloom filter can be proven to be impossible, sadly.

<i>With enough data, a traditional Bloom filter &quot;fills up&quot;, after which it has a false-positive probability of 1.</i><p>I don&#x27;t think this correct. The false-positive probability wouldn&#x27;t become 1, it&#x27;s just that every query would return positive, regardless if it&#x27;s a true or false positive. I think what you meant to say was that the positive probability is 1, not the false-positive probability.

Why does the readme use Boom and Bloom interchangeably? Is it just a typo that for some reason is randomly scattered throughout the document (and in the repo name itself)? Or is there meant to be a difference? I don&#x27;t see anywhere that the difference is explained, if it&#x27;s intentional.

You should checkout Tyler&#x27;s blog. Good solid content for the concurrency geeks.