| Title | : | Fading BF: A Bloom Filter with Graceful Decay for Online Networking Applications |
| Speaker | : | Prasanna Karthik V (IITM) |
| Details | : | Fri, 6 Mar, 2020 12:00 PM @ MR1-ALC |
| Abstract: | : | Bloom filter is a storage-efficient data structure for storing set membership
information. It supports inserts and queries but does not support delete operations.
Online applications that use Bloom filters have suffered from its lack of support to
decay/delete stale elements, in the absence of which the Bloom filter gets quickly
saturated. Existing mechanisms for
decay either require unreasonable storage and computation to safely decay elements,
or use relatively inexpensive techniques that gracelessly delete a large number of
elements in an instant, causing correctness or performance issues in applications.
The lack of an efficient decay method in Bloom filters is well-known in the
literature. In this work, we propose Fading Bloom filter (Fading BF), a novel variant of the Bloom filter, which can provide safe decay of elements. Fading BF neither requires additional storage nor computation to achieve this but instead exploits the intrinsic properties of the underlying storage medium, i.e., of DRAM capacitors. We realize Fading BF by implementing the standard Bloom filter on a DRAM memory module but with its periodic refresh disabled. With periodic refresh disabled, the cells holding the data elements that are not accessed frequently will predictably lose charge and will naturally decay. The retention time of capacitors guarantees that elements are not decayed too soon. However, some elements may be stored longer than required due to the software and hardware variables of the Fading BF, namely, its size, the number of hash functions, and the DRAM layout. Using an analytical model of the Fading BF, we show that carefully tuning its parameters can minimize such cases. For a networking application that measures QoS of devices, we demonstrate that Fading BF achieves better guarantees through graceful decay. |
