Bloom Filter

Bloom Filter is a probabilistic data structure for membership filter. Burton Howard Bloom introduced an approximate membership filtering data structure in 1970. Hence, it is called as Bloom Filter. Since its inception, Bloom Filter has been extensively experimented with and developed to enhance system performance such as web cache. Bloom Filter influences many research fields, including Bioinformatics, Internet of Things, computer security, network appliances, Big Data, and Cloud Computing. Bloom Filter has been propelled to the forefront of the hashing algorithm, and it has become even more important in recent years due to its dramatic improvement of query and memory performance. Bloom Filter utilizes a tiny amount of memory space to keep a record of huge sets of data, for example, in Network Packet Filtering.

Bloom Filter: A Data Structure for Computer Networking, Big Data, Cloud Computing, Internet of Things, Bioinformatics, and Beyond focuses on both theory and practice of most emerging areas for Bloom Filter application, including Big Data, Cloud Computing, Internet of Things, and Bioinformatics. Part I provides indepth insight on Bloom Filter data structure and its variants. Part II focuses on the role of Bloom Filter in Computer Networking. Part III focuses on applications of Bloom Filter in various research domains, such as Big Data, Cloud Computing, and Bioinformatics.

The applications of Bloom Filter are vast. Big Table uses Bloom Filter to eliminate unnecessary HDD accesses which in turn boosts the performance of the whole system. Similarly, storage deduplication, content-centric network, and data streaming also deploy Bloom Filter to minimize memory consumption. Bloom Filter is also applied in the P2P model to improve lookup performance. Bloom Filter is also used to remove redundant recommendation in recommender system. Moreover, the storage performance of the Metadata Server is boosted by deploying Bloom Filter. The conventional Metadata Server uses a hashing system or tree; however, using the Bloom Filter reduces memory consumption in terms of an order of magnitude. URL deduplication removes duplicate URLs using Bloom Filter. Furthermore, the Bloom Filter is prominently used in the implementation of cache memory, and there are many applications of Bloom Filter in Biometric and Biomedical Engineering applications. Other applications of Bloom Filter include error correction, Wireless Sensor Networks, Plagiarism checking, Web search, searchable encryption schemes, Internet of Things, databases and cloud data filtering. It is also applied in interdisciplinary computing applications such as DNA Sequencing.

The reader will learn about the theory and structure of Bloom Filter, its various applications, as well as exploring some of the many variants of Bloom Filter that have been introduced, including CountBF, Cuckoo Filter, dlCBF, Quotient Filter, Scalable Bloom Filter, Sliding Bloom Filter, TinySet, Ternary Bloom Filter, Bloofi, Deletable Bloom Filter, and Dynamic Reordering Bloom Filter, BloomStore, Forest-Structured Bloom Filter, and BloomFlash.