Abstract:

This paper presents a multilevel structure called the Treebased Bloom Filter(TBF). Multilevel structure is the hot spots of Bloom filters and related data structure research in recent years. This structure achieves multiple levels of storage and reduces the burden of onchip memory, but it also accelerates the speed of onchip search. TBF is a more efficient algorithm which is the improvement based on the drawbacks of the BloomingTree algorithm, and TBF can reduce the conditions of the space requirements and achieve the same function of CBF under the same conditions. Our experiments show that compared with the BloomingTree algorithm, the TBF algorithm can effectively solve the index error in the logic problem of the BloomingTree algorithm, and show more time efficiency: under the conditions of the same false positiveness  and unchanged layers, the query time improve on  an average of 13.4%; under the conditions of the fixed false positiveness and the same layer changes, the time of insertion improves on an average of 17.9%, and 12% average improve the time of deletion.

Key words: Bloom filter;multilevel structure;data structure;set element search