카운팅 블룸필터를 대체하는 터너리 블룸 필터

Counting Bloom filters (CBFs) have been popularly used in many applications for the membership queries of dynamic sets, since CBFs can provide delete operations. A CBF uses an array of c-bit counters. The c should be chosen large enough to avoid overflows, and 4 bits are known to suffice for most applications. However, the CBF composed of 4-bit counters wastes memory spaces by allocating 4 bits for every counter, even though around the half of the counter values are zeros in an optimally programmed Bloom filter. In this paper, we propose a simple alternative of a CBF named ternary Bloom filter (TBF). When the TBF consumes the same amount of memory space as a CBF, it is shown that the TBF provides a better false positive rate than the CBF.