A Bloom Filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. A Counting Bloom Filter (CBF) allows the same operations on dynamical sets that can be updated via insertions and deletions with larger memory requirements. This paper presents a novel hierarchical data structure, called Blooming Tree, that replicates the functionalities of a CBF with lower memory consumption and tunable false positive probability. The hierarchical multi-layer design of Blooming Trees allows for distributing the structure in different memory levels, thus exploiting small but fast on-chip memories for most frequently accessed substructures. The proposed algorithm is compared to previous existing schemes on a target platform: Intel IXP2XXX Network Processors (NPs).
Titolo: | Blooming trees: Space-efficient structures for data representation |
Autori interni: | |
Anno del prodotto: | 2008 |
Rivista: | |
Abstract: | A Bloom Filter is an efficient randomized data structure for membership queries on a set with a certain known false positive probability. A Counting Bloom Filter (CBF) allows the same operations on dynamical sets that can be updated via insertions and deletions with larger memory requirements. This paper presents a novel hierarchical data structure, called Blooming Tree, that replicates the functionalities of a CBF with lower memory consumption and tunable false positive probability. The hierarchical multi-layer design of Blooming Trees allows for distributing the structure in different memory levels, thus exploiting small but fast on-chip memories for most frequently accessed substructures. The proposed algorithm is compared to previous existing schemes on a target platform: Intel IXP2XXX Network Processors (NPs). |
Handle: | http://hdl.handle.net/11568/200708 |
ISBN: | 9781424420759 |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |