Sliding Bloom Filter

A Sliding Bloom filter (or Rolling Bloom filter) is a type of Bloom filter that stores the last n values (a sliding window). Old values are evicted based on time or fill ratio.


Here's an illustration with two sub filters:

Currently in combined filter: 17 8 4 12 55 7 31 72 2 To insert: 17 8 4 12 55 7 31 72 2


Sliding Bloom filters can be used when a time retention policy must be implemented, for example due to contractual, legislative or security reasons.

Example: The owner of a webshop that accepts credit card payments would like to track the number of returning customers. To see if a credit card numbers has been used before, credit card numbers are stored in a Bloom filter. Due to data retention policies, old credit card numbers must be discarded, thus a Sliding Bloom filter is a good fit.

If a Bloom filter needs to keep track of an ever growing set of elements (an infinite stream), a Sliding Bloom filters can be used as an approximation.

Example: Content delivery networks (CDNs) usually cache responses for previous requests. Many requests however are so called "one hit wonders"—requests made once then never again. To avoid caching such requests, it's common to implement a cache-on-second-hit rule: Responses are cached the second time around. To determine if a request has been seen before, a sliding Bloom filter is used. This is suitable since there is a never ending stream of requests. (Source: Algorithmic Nuggets in Content Delivery)


Be the first to comment!