TY - GEN
T1 - Ternary bloom filter replacing counting bloom filter
AU - Byun, Hayoung
AU - Lee, Jungwon
AU - Lim, Hyesook
N1 - Funding Information:
This research was supported by the National Research Foundation of Korea (NRF), NRF-2014R1A2A1A11051762 and NRF-2015R1A2A1A15054081. This research was also supported by the Ministry of Science, ICT and Future Planning (MSIP), Korea, under the Information Technology Research Center (ITRC) support program (IITP-2015-H8501-15-1007) supervised by the Institute for Information & communications Technology Promotion (IITP).
Publisher Copyright:
© 2016 IEEE.
PY - 2017/1/3
Y1 - 2017/1/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85011022631&partnerID=8YFLogxK
U2 - 10.1109/ICCE-Asia.2016.7804774
DO - 10.1109/ICCE-Asia.2016.7804774
M3 - Conference contribution
AN - SCOPUS:85011022631
T3 - 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
BT - 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
Y2 - 26 October 2016 through 28 October 2016
ER -