Complement Bloom Filter for Identifying True Positiveness of a Bloom Filter
Authors:
- 14 September 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Communications Letters
- Vol. 19 (11) , 1905-1908
Abstract
The use of Bloom filters in network applications has increased rapidly. Since Bloom filters can produce false positives, the trueness of each positive needs to be identified by referring to an off-chip hash table. This letter proposes a new method for identifying the trueness of Bloom filter positives. We propose the use of an additional Bloom filter programmed for the complement set of the given set. In querying an input, if the complement Bloom filter produces a negative result, the input is a member of the given set since Bloom filters never produce a false negative. When both Bloom filters produce positives, a hash table needs to be referred to in our method. We provide a mathematical analysis, whereby the probability of referring to a hash table converges to the summation of the false positive probabilities of each Bloom filter. We provide the simulation result that the rate of referring to a hash table in our method is the order of 10 -5 for Bloom filter sizing factor 32.Keywords
Funding Information
- National Research Foundation of Korea (NRF)
- Korea government (MEST) ((2014R1A2A1A11051762))
- MSIP (Ministry of Science, ICT and Future Planning)
- Information Technology Research Center (ITRC) ((IITP-2015-H8501-15-1007))
- Institute for Information & communications Technology Promotion (IITP)
- Basic Science Research Program through the National Research Foundation of Korea (NRF)
- Ministry of Education, Science and Technology ((20110009426))
This publication has 9 references indexed in Scilit:
- New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based AlgorithmsIEEE Transactions on Computers, 2015
- Named data networkingACM SIGCOMM Computer Communication Review, 2014
- Reducing False Positives of a Bloom Filter using Cross-Checking Bloom FiltersApplied Mathematics & Information Sciences, 2014
- Scalable Pending Interest Table design: From principles to practice2014
- On Adding Bloom Filters to Longest Prefix Matching AlgorithmsIEEE Transactions on Computers, 2012
- The deletable Bloom filter: a new member of the Bloom familyIEEE Communications Letters, 2010
- Less Hashing, Same Performance: Building a Better Bloom Filter2006
- Compressed Bloom filtersIEEE/ACM Transactions on Networking, 2002
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970