Optimization and Applications of Dynamic Bloom Filters
Main Article Content
Abstract
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
Downloads
Article Details
COPYRIGHT
Submission of a manuscript implies: that the work described has not been published before, that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
- The journal allows the author(s) to retain publishing rights without restrictions.
- The journal allows the author(s) to hold the copyright without restrictions.