Optimization and Applications of Dynamic Bloom Filters

Main Article Content

M.M.Siva Krishna
V.Bala Sankar


Bloom Filters (BF) are space-efficient data structures that allow membership queries from a set. The Bloom Filters and its variants just focus on how to represent a static set and decrease the false probability to a sufficiently low level. By look into the applications based on the Bloom Filters, we reveal that dynamic datasets are more common and important than static sets. But the existing variants of the Bloom Filters cannot support dynamic data sets well. To address this issue Dynamic Bloom Filters (DBF) has been proposed as a method to implement Bloom Filters in a scalable environment, i.e. where the final size of a dataset is not known in advance. DBF seems to be a logical addition to BF for a scalable environment - just before the false positive (FP) rate of a particular BF starts growing fast, we simply switch to a new filter and store the old one.DBF handles inserts and lookups. We present multi-dimension dynamic bloom filters (MDDBF) to support concise representation and approximate membership queries of dynamic sets in multiple attribute dimensions, and study the false positive probability and union algebra operations. We also explore the optimization approach and three network applications of bloom filters, namely bloom joins, informed search, and global index implementation.


Key words: BF, FP, DBF, MDDBF


Download data is not yet available.

Article Details