A new Bloom filter structure for identifying true positiveness of a Bloom filter
Authors:
- 1 June 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-5
Abstract
Bloom filters have been employed in various fields because of its simple and effective structure in identifying the membership of an input. Since a Bloom filter can produce false positives, the positive results of a Bloom filter should be identified whether the positives are true or not by accessing the original database. A complement Bloom filter (C-BF) was introduced to identify the true positiveness of a given Bloom filter without accessing the original database. A critical problem of the C-BF is that every element included in the complement set of the given set should be programmed into the C-BF. Since the number of elements included in the complement set can be considerably large, the C-BF would require the significant amount of memory. In this paper, we claim that the elements that produce negative results from the given Bloom filter are not necessarily programmed into the C-BF, since Bloom filters never produce false negatives. In other words, we propose the Petit-BF (P-BF) which programs only the elements that cause false positives from the given Bloom filter. Simulation results and theoretical analysis show that the proposed method can achieve the same performance using a considerably smaller amount of memory.Keywords
This publication has 12 references indexed in Scilit:
- Complement Bloom Filter for Identifying True Positiveness of a Bloom FilterIEEE Communications Letters, 2015
- New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based AlgorithmsIEEE Transactions on Computers, 2015
- Reducing False Positives of a Bloom Filter using Cross-Checking Bloom FiltersApplied Mathematics & Information Sciences, 2014
- NameFilter: Achieving fast name lookup with low memory cost via applying two-stage Bloom filters2013
- On Adding Bloom Filters to Longest Prefix Matching AlgorithmsIEEE Transactions on Computers, 2012
- Theory and Practice of Bloom Filters for Distributed SystemsIEEE Communications Surveys & Tutorials, 2011
- Beyond bloom filtersACM SIGCOMM Computer Communication Review, 2006
- Longest prefix matching using bloom filtersIEEE/ACM Transactions on Networking, 2006
- Summary cache1998
- A linear-time probabilistic counting algorithm for database applicationsACM Transactions on Database Systems, 1990