Bloom Filter: A Data Structure for Computer Networking, Big Data, Cloud Computing, Internet of Things, Bioinformatics and Beyond

Front Cover
Bloom Filter
Copyright
Contents
Preface
Acknowledgments
I Bloom Filters
1 Introduction
1.1 Introduction
1.2 Organization
References
2 Bloom Filters: a powerful membership data structure
2.1 Introduction
2.1.1 Motivation
2.1.2 Contribution
2.1.3 Organization
2.2 Bloom Filter
2.2.1 Architecture of Bloom Filter
2.2.2 Operations of Bloom Filter
2.2.2.1 Insertion
2.2.2.2 Lookup
2.2.2.3 Deletion
2.3 Bit array
2.4 Taxonomy of response
2.4.1 True positive
2.4.2 True negative
2.4.3 False positive
2.4.4 False negative
2.5 Key objectives
2.5.1 Reduction of the number of false positives
2.5.2 Reduction of the number of false negatives
2.5.3 Increment of scalability
2.5.4 Maximization of performance
2.6 Taxonomy of Bloom Filter
2.6.1 Architecture
2.6.1.1 Counting Bloom Filter
2.6.1.2 Non-counting Bloom Filter
2.6.2 Memory allocation
2.6.2.1 Static Bloom Filter
2.6.2.2 Dynamic Bloom Filter
2.6.3 Implementation
2.6.3.1 Flat Bloom Filter
2.6.3.2 Block-based Bloom Filter
2.6.3.3 Hierarchical Bloom Filter
2.6.3.4 Chained Bloom Filter
2.6.3.5 Multidimensional Bloom Filter
2.6.4 Platform
2.6.4.1 Cache-based Bloom Filter
2.6.4.2 RAM-based Bloom Filter
2.6.4.3 Flash/SSD-based Bloom Filter
2.6.4.4 HDD-based Bloom Filter
2.7 Analysis of false positive
2.8 Lessons learned
2.9 Conclusion
Appendix 2.A Source code of Bloom Filter
Appendix 2.B Symbols used in the chapter
References
3 robustBF: a high accuracy and memory efficient 2D Bloom Filter for diverse applications
3.1 Introduction
3.2 Preliminaries
3.2.1 Operations
3.3 robustBF – the proposed system
3.3.1 Selection of a hash function
3.3.2 Insertion
3.3.3 Lookup
3.4 Experimental results
3.4.1 Test cases
3.4.2 Experiments
3.4.3 Hash function experiments
3.4.4 Comparison of robustBF with other filters
3.5 Analysis
3.5.1 Memory requirements of robustBF
3.5.2 Comparison of robustBF with other filters
3.6 Conclusion
References
4 Impact of the hash functions in Bloom Filter design
4.1 Introduction
4.2 Hash functions
4.3 Prime numbers in Bloom Filter
4.4 Number of hash functions
4.5 Types of hash functions
4.6 Comparison of robustBF and libbloom
4.7 Conclusion
References
5 Analysis on Bloom Filter: performance, memory, and false positive probability
5.1 Introduction
5.2 False positive probability
5.2.1 Approximate false positive analysis
5.2.2 Exact false positive analysis
5.3 Memory
5.4 Performance
5.4.1 Dataset
5.4.2 Bloom Filter settings
5.4.3 Experimental results
5.5 Conclusion
References
6 Does not Bloom Filter bloom in membership filtering?
6.1 Introduction
6.2 Bloom Filter is not a complete system!
6.2.1 Limitations of Bloom Filter
6.2.2 Applicability of Bloom Filter
6.3 Learned Bloom Filter
6.4 Malicious URL filtering using Bloom Filter
6.5 Conclusion
References
7 Standard of Bloom Filter: a review
7.1 Introduction
7.2 Literature review on standard Bloom Filter
7.3 Other approximation filters
7.4 Conclusion
References
8 Counting Bloom Filter: architecture and applications
8.1 Introduction
8.2 Counting Bloom Filter
8.2.1 Architecture
8.2.2 Operations of CBF
8.2.2.1 Insertion
8.2.2.2 Lookup
8.2.2.3 Deletion
8.2.3 First counting Bloom Filter
8.2.4 Analysis
8.3 Variants
8.3.1 Space-code Bloom Filter (SCBF)
8.3.2 Linked counting Bloom Filter
8.3.3 L-counting Bloom Filter (L-CBF)
8.3.4 d-left counting Bloom Filter
8.3.5 Variable-length counting Bloom Filter (VLCBF)
8.3.6 Balanced counting Bloom Filters (BCBFs)
8.3.7 Floating counter Bloom Filter (FCBF)
8.3.8 Detached counting Bloom array (DCBA)
8.3.9 Cache-based counting Bloom Filter (C2BF)
8.3.10 Compressed counting Bloom Filter (CCBF)
8.3.11 Temporal counting Bloom Filter (TCBF)
8.3.12 Double layer counting Bloom Filter (DLCBF)
8.3.13 Fingerprint counting Bloom Filter (FP-CBF)
8.3.14 Wrap-around counting Bloom Filter (WCBF)
8.3.15 Counting quotient filter (CQF)
8.3.16 Dual counting Bloom Filter (DCBF)
8.4 Issues
8.5 Conclusion
References
9 Hierarchical Bloom Filter
9.1 Introduction
9.2 Variants
9.2.1 Hierarchical Bloom Filter array (HBA)
9.2.2 Multi-granularities counting Bloom Filter (MGCBF)
9.2.3 Cached counting Bloom Filter (CCBF)
9.2.4 Hierarchical counting Bloom Filters (HCBF)
9.2.5 Blooming tree
9.2.6 Multilayer compressed counting Bloom Filter (ML-CCBF)
9.2.7 Multilevel counting Bloom Filter (MLCBF)
9.2.8 Reversible multilayer hashed counting Bloom Filter (RML-HCBF)
9.2.9 Multiple-partitioned counting Bloom Filter (MPCBF)
9.2.10 Bloofi
9.3 Issues
9.4 Applications
9.4.1 MapReduce
9.4.2 Distributed system
9.5 Conclusion
References
II Applications of Bloom Filter in networking
10 Applications of Bloom Filter in networking and communication
10.1 Introduction
10.2 Traffic management
10.2.1 Traffic statistics
10.3 Packet management
10.4 Routing
10.5 Searching
10.5.1 Prefix matching
10.6 Discussion
10.7 Conclusion
References
11 Bloom Filter for named-data networking
11.1 Introduction
11.2 Named data networking
11.3 Named data networking packet
11.3.1 Bloom Filter in the packet
11.3.2 Content discovery
11.4 Content store
11.5 Pending interest table
11.6 Forwarding information base
11.7 Security
11.8 Discussion
11.9 Conclusion
References
12 Enhancement of software-defined networking using Bloom Filter
12.1 Introduction
12.2 SDN architecture
12.2.1 Interfaces
12.3 Control layer
12.3.1 Architecture
12.3.2 Network monitoring
12.4 Data layer
12.4.1 OpenFlow
12.4.2 ForCES
12.4.3 Review
12.5 Issues and challenges
12.6 Security
12.7 Discussion
12.8 Conclusion
References
13 Impact of Bloom Filter in wireless network
13.1 Introduction
13.2 Wireless sensor networks
13.2.1 Security
13.3 Mobile ad-hoc networks
13.4 Internet-of-Things
13.5 Discussion
13.6 Conclusion
References
14 Network security using Bloom Filter
14.1 Introduction
14.2 DDoS
14.2.1 Types of DDoS attacks
14.2.2 Defense techniques against DDoS
14.2.2.1 Link flooding attack
14.2.2.2 Interest flooding attack
14.2.2.3 Data flooding attack in ICN
14.3 DoS
14.3.1 Defense techniques against DoS
14.3.1.1 SIP
14.4 Defense against various network attacks
14.4.1 Pollution attack
14.4.2 Query-only attack
14.4.3 Deletion attack
14.4.4 Brute force and dictionary attacks
14.5 Security
14.6 Privacy
14.7 Evaluation
14.8 Discussion
14.8.1 False negative
14.8.2 False positive
14.9 Conclusion
References
III Applications of Bloom Filter in other domains
15 Applications of Bloom Filter in Big data
15.1 Introduction
15.2 Data management
15.3 Database
15.3.1 Privacy-preserving record linkage
15.4 MapReduce
15.5 Discussion
15.6 Conclusion
References
16 Bloom Filter in cloud computing
16.1 Introduction
16.2 Indexing and searching of encrypted data
16.3 Cloud data storage management
16.4 Discussion
16.5 Conclusion
References
17 Applications of Bloom Filter in biometrics
17.1 Introduction
17.2 Biometrics
17.3 Cancelable biometrics
17.4 Discussion
17.5 Conclusion
References
18 Bloom Filter for bioinformatics
18.1 Introduction
18.2 Preprocessing filtering
18.2.1 k-mer counting
18.2.2 Read compression
18.2.3 Error correction
18.3 de Bruijn graph
18.4 Searching
18.5 DNA assembly technique
18.6 Other bioinformatics areas
18.6.1 Genome annotation
18.6.2 Pan-genomics
18.6.3 Genetics of diseases
18.7 Discussion
18.8 Conclusion
References
Index
Back Cover