Ternary bloom filter replacing counting bloom filter
- 등재 SCOPUS
- 발행기관 Institute of Electrical and Electronics Engineers Inc.
- 발행년도 2016
- 총서유형 Journal
- 회의명 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
- 일자 26 October 2016 through 28 October 2016
- URI http://www.dcollection.net/handler/ewha/000000141677
- ISBN 9781509027439
- 본문언어 영어
- Published As http://dx.doi.org/10.1109/ICCE-Asia.2016.7804774
초록/요약
A counting Bloom filter (CBF) generalizes a standard 1-bit vector Bloom filter and allows not only membership queries but also insertion and deletion operations for dynamic sets. However, the CBF can cause false negatives because of counter overflows. A 4-bit vector CBF, which provides the probability of false negatives sufficiently small, is generally used. However, the 4-bit vector CBF wastes memory space by allocating 4 bits for every counter, even though the half of counter values of the CBF is zero. This paper proposes a Ternary Bloom filter (TBF) which is a variation of the CBF. The TBF is motivated to use the minimum number of bits for each counter and constructs a larger Bloom filter instead. In the TBF, counters mapped with two or more number of elements are represented by X, and the counters with value X are not used in insertion, deletion, or querying operations. Since a larger Bloom filter can reference more number of counter values, the proposed TBF improves false positive rate than the CBF which consumes the same amount of memory, and the proposed TBF also removes false negative problem. © 2016 IEEE.
more