一种基于树形结构的布鲁姆过滤器  

Bloom Filters Based on the Tree Structure

作　　者：程聂[1] 黄昆[1] 苏欣[1] 张大方[1] 

机构地区：[1]湖南大学软件学院,湖南长沙410082

出　　处：《计算机工程与科学》2012年第2期19-24,共6页Computer Engineering & Science

基　　金：国家发改委信息安全专项(发改办高技[2009]1886号文);湖南省科技计划重点项目(2009JT1018)

摘　　要：本文提出一种基于多层次结构的树形布鲁姆过滤器TBF。多层次结构是近年来布鲁姆过滤器及相关数据结构研究的热点。这一结构使得多层次的存储方式得以实现,减轻了片上存储的负担,而且也加快了片上查找的速度。TBF是针对BloomingTree算法存在的缺陷所改进的一种更高效的算法,它能够在低于CBF的空间需求的条件下实现与CBF相同的功能。实验证明:与BloomingTree算法相比,TBF能够有效地解决BloomingTree算法在逻辑索引时的错误问题,而且比BloomingTree算法时间上更加高效:在层数不变假阳性相同条件下,查询时间平均提高13.4%;在假阳性不变层数相同条件下,插入时间平均提高17.9%,删除时间平均提高12%。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.

关 键 词：布鲁姆过滤器 多层次结构 数据结构 集合元素查询 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]