计算机工程与科学2012，Vol.34Issue(2)：19-24,6.DOI:10.3969/j.issn.1007-130X.2012.02.004
一种基于树形结构的布鲁姆过滤器
Bloom Filters Based on the Tree Structure
摘要
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分类
信息技术与安全科学引用本文复制引用
程聂,黄昆,苏欣,张大方..一种基于树形结构的布鲁姆过滤器[J].计算机工程与科学,2012,34(2):19-24,6.基金项目
国家发改委信息安全专项(发改办高技[2009]1886号文) （发改办高技[2009]1886号文）
湖南省科技计划重点项目(2009JT1018) （2009JT1018）
