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

• 作者: 张大方 程聂 苏欣 黄昆
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 布鲁姆过滤器 多层次结构 数据结构 集合元素查询
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 19-24
• 分类号: TP393
• 字数: 5582字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2012.02.004

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张大方	湖南大学软件学院	295	2498	22.0	33.0
2	黄昆	湖南大学软件学院	18	337	9.0	18.0
3	程聂	湖南大学软件学院	1	1	1.0	1.0
4	苏欣	湖南大学软件学院	10	51	5.0	7.0