Conference Paper
Title: MultiLayer Compressed Counting Bloom Filters
Authors: Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci

Conference: INFOCOM 2008, 15-17 April, Phoenix, USA
Abstract: Bloom Filters are efficient andomized 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 Counting Bloom Filters. This bound is much tighter than that usually adopted in literature and it allows for designing improvements to standard CBFs. Based on these results, three new data structures are proposed. They 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: 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 (NPs).