基于树形结构的布鲁姆过滤器研究

论文摘要

布鲁姆过滤器算法凭借其简单迅捷的查询方式和优异的空间效率而受到了广泛关注,但是布鲁姆过滤器算法并不能支持数据集成员的动态更新尤其是不能支持数据集成员的删除操作,因为删除操作会引起布鲁姆过滤器的误判,从而影响查询的准确性即降低查询的精度；计数式布鲁姆过滤器算法使用Coutner计数器替代布鲁姆过滤器中的比特位,因此能够很好地支持数据集成员的动态更新,但是使用计数器也存在着空间开销过大的问题。关于布鲁姆过滤器算法的各种研究针对布鲁姆过滤器在空间开销、时间开销、查询精度三个方面的效率提出了多种行之有效的改进方案。本文针对以上三种性能指标,提出了一种基于多层次结构的树形布鲁姆过滤器（Tree-based Bloom Filter简称TBF）。多层次结构的TBF算法是基于BloomingTree算法在空间开销上的优势,并针对其所存在的缺陷设计的一种更加快速高效的算法。TBF查询、更新方法是从寻找更有效的方法,来替代原来BloomingTree算法中容易导致错误的逻辑索引方式,并减少原方法在每一层都必须进行的比特位查询确认操作这两个方面来进行考虑,改进与设计了TBF算法的查询索引方式和与之相应的更新算法。通过新的更加快速高效的查询索引方式,能够迅速、有效的查找到应该执行查询、更新的相应位置或相应比特位,从而完成对数据集中数据成员的查询匹配,或是对数据集成员的更新工作；而TBF查询算法通过减少比特位确认操作,提高了TBF查询和更新的速度,节省了时间开销。TBF算法能够在低于计数式布鲁姆过滤器的空间需求的条件下实现与计数式布鲁姆过滤器相同的功能,而且TBF算法比之BloomingTree算法更加快速高效。经过实验证明：与BloomingTree算法相比,TBF算法能够有效的解决BloomingTree算法在逻辑索引时所存在的错误查询问题,而且比BloomingTree算法时间上更加高效：在层数不变假阳性相同条件下,查询时间平均提高13.4%；在假阳性不变层数相同条件下,插入时间平均提高17.9%,删除时间平均提高12%。因此,TBF查询、更新算法具有其可行性,它在空间效率、时间效率和查询精度三方面取得明显的改进,增强了布鲁姆过滤器及其相关研究的扩展性,能够为网络数据存储表示和数据集合中数据成员查询提供保障。

论文目录

• 摘要
• Abstract
• 插图索引
• 第1章 绪论
• 1.1 互联网面临的挑战
• 1.2 布鲁姆过滤器的出现及其意义
• 1.3 国内外研究现状
• 1.3.1 布鲁姆过滤器
• 1.3.2 计数式布鲁姆过滤器
• 1.3.3 压缩布鲁姆过滤器
• 1.3.4 光谱布鲁姆过滤器
• 1.3.5 动态布鲁姆过滤器
• 1.3.6 多维布鲁姆过滤器
• 1.3.7 动态计数过滤器
• 1.3.8 D-left计数布鲁姆过滤器
• 1.3.9 BloomingTree算法
• 1.4 本文主要内容
• 1.5 本文结构
• 第2章 布鲁姆过滤器相关研究综述
• 2.1 查询算法简介
• 2.2 哈希查询算法
• 2.2.1 哈希查询算法原理及应用
• 2.2.2 哈希查询算法的性能分析
• 2.3 布鲁姆过滤器查询算法
• 2.3.1 布鲁姆过滤器查询算法原理
• 2.3.2 布鲁姆过滤器查询算法性能分析
• 2.4 布鲁姆过滤器改进算法
• 2.4.1 计数式布鲁姆过滤器查询算法
• 2.4.2 BloomingTree查询算法
• 2.5 本章小结
• 第3章 树形布鲁姆过滤器查询算法
• 3.1 树形的由来
• 3.2 TBF查询算法
• 3.2.1 TBF查询算法原理
• 3.2.2 TBF查询算法具体步骤
• 3.3 TBF更新算法
• 3.3.1 TBF更新算法原理
• 3.3.2 TBF更新算法具体步骤
• 3.4 冲突解决策略
• 3.4.1 冲突的产生
• 3.4.2 设计冲突解决策略
• 3.4.3 冲突解决策略的具体步骤
• 3.5 TBF查询算法的性能分析
• 3.6 本章小结
• 第4章 TBF算法的仿真实验
• 4.1 实验目的与需求
• 4.2 流程设计与实验环境
• 4.2.1 程序流程设计
• 4.2.2 实验环境与准备
• 4.3 实验结果与分析
• 4.3.1 验证TBF查询算法
• 4.3.2 验证TBF更新算法
• 4.3.3 实验结果分析说明
• 4.4 本章小结
• 结论
• 参考文献
• 附录A 攻读学位期间所发表的学术论文目录
• 致谢