Age-Partitioned Bloom Filters

This is really great!<p>For those that don&#x27;t know, bloom filters are really good at determining when something is not in a set. So if says &quot;not in set&quot; that&#x27;s 100% accurate and super fast.<p>We used this to our advantage at reddit. When you load a comments page, we had to determine if you&#x27;ve voted on anything. So with the bloom filter in front, the query for &quot;have they voted on anything here&quot; was very quick if the answer was no.<p>But we still had to make the query. So another hack we did was to put a value on your user object to track the last time you interacted with the website. If the comments page was made after your last interaction, then we didn&#x27;t even have to do the query.<p>With this, we wouldn&#x27;t have to do the two step process -- it sounds like this would be super fast when it was time boxed. Maybe...

Aether (<a href="https:&#x2F;&#x2F;getaether.net" rel="nofollow">https:&#x2F;&#x2F;getaether.net</a>) also uses a roughly equivalent version of this I had thought, up to this point, that I ‘discovered’. I call it ‘Rolling Bloom’. (Not sure which implementation is first.)<p>Here’s the Go implementation: <a href="https:&#x2F;&#x2F;github.com&#x2F;nehbit&#x2F;aether&#x2F;blob&#x2F;master&#x2F;aether-core&#x2F;aether&#x2F;services&#x2F;rollingbloom&#x2F;rollingbloom.go" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;nehbit&#x2F;aether&#x2F;blob&#x2F;master&#x2F;aether-core&#x2F;aet...</a>

I&#x27;ve used something like this before, thank you for characterizing it. :- )<p>I used mine for authentication rejection.

Missed opportunity to title this paper &quot;OK Bloomer&quot;.

An interesting hack is to use a count-based bloom filter, maybe 8-bits per count instead of 1-bit.<p>As long as the &quot;count&quot; doesn&#x27;t overflow to the max size (in this case: 255), you can always &quot;remove&quot; items from a Counting Bloom Filter. In effect, a traditional 1-bit bloom filter is simply a counting-bloom filter that &quot;overflows&quot; on the first hit.<p>If people really need deletion on their bloom filter, do realize it is possible! (as long as you select a proper bit-size).