MultiLayer Compressed Counting Bloom Filters

Abstract

Bloom filters are efficient randomized data structures for membership queries on a set with a certain known false positive probability. Counting bloom filters (CBFs) allow the same operation on dynamic sets that can be updated via insertions and deletions with larger memory requirements. This paper first presents a new upper bound for counters overflow probability in CBFs. This bound is much tighter than that usually adopted in literature and it allows for designing more efficient CBFs. Three novel data structures are proposed, which introduce the idea of a hierarchical structure as well as the use of Huffman code. Our algorithms improve standard CBFs in terms of fast access and limited memory consumption (up to 50% of memory saving): the target could be the implementation of the compressed data structures in the small (but fast) local memory or "on-chip SRAM" of devices such as network processors .