Ternary bloom filter replacing counting bloom filter

Hayoung Byun, Jungwon Lee, Hyesook Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509027439
DOIs
StatePublished - 3 Jan 2017
Event2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016 - Seoul, Korea, Republic of
Duration: 26 Oct 201628 Oct 2016

Publication series

Name2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016

Conference

Conference2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
Country/TerritoryKorea, Republic of
CitySeoul
Period26/10/1628/10/16

Fingerprint

Dive into the research topics of 'Ternary bloom filter replacing counting bloom filter'. Together they form a unique fingerprint.

Cite this