Name
Abstract | ||
|---|---|---|
Bloom Filters are efficient randomized data struc- tures 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. Index Terms—Counting Bloom Filter, Huffman coding, Net- work Processor, Hashing functions, MultiLayer structure counters are incremented; deletions can now be safely done by decrementing the counters. CBFs present the problem of counters overflow, which has to be considered in the design. This paper presents a new upper bound for overflow proba- bility in CBFs. This bound is much tighter than that commonly utilized in literature and it is useful for our design of efficient solutions. Thus, three new data structures are proposed, which take advantage of the bound and improve CBFs in terms of fast access and limited memory consumption (up to 50% of memory saving in comparison with the standard solutions). 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). |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/INFOCOM.2008.71 | Phoenix, AZ |
Keywords | Field | DocType |
Huffman codes,SRAM chips,data structures,filters,Huffman code,compressed multilayer,counters overflow probability,counting bloom filters,data structures,network processors,on-chip SRAM | Network processor,Bloom filter,Data structure,Computer science,Upper and lower bounds,Parallel computing,Network on a chip,Static random-access memory,Huffman coding,Memory management | Conference |
ISSN | ISBN | Citations |
0743-166X | 978-1-4244-2025-4 | 22 |
PageRank | References | Authors |
0.99 | 8 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Domenico Ficara | 1 | 23 | 1.37 |
| Giordano, S. | 2 | 72 | 9.11 |
| Gregorio Procissi | 3 | 24 | 1.38 |
| Fabio Vitucci | 4 | 22 | 0.99 |