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

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

Bloom Filters Based on the Tree Structure

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.