一种基于树形结构的布鲁姆过滤器
【出 处】:《
计算机工程与科学
》
CSCD
2012年第34卷第2期 19-24页,共6页
【作 者】:
程聂
;
黄昆
;
苏欣
;
张大方
【摘 要】
本文提出一种基于多层次结构的树形布鲁姆过滤器TBF。多层次结构是近年来布鲁姆过滤器及相关数据结构研究的热点。这一结构使得多层次的存储方式得以实现,减轻了片上存储的负担,而且也加快了片上查找的速度。TBF是针对BloomingTree算法存在的缺陷所改进的一种更高效的算法,它能够在低于CBF的空间需求的条件下实现与CBF相同的功能。实验证明:与BloomingTree算法相比,TBF能够有效地解决BloomingTree算法在逻辑索引时的错误问题,而且比BloomingTree算法时间上更加高效:在层数不变假阳性相同条件下,查询时间平均提高13.4%;在假阳性不变层数相同条件下,插入时间平均提高17.9%,删除时间平均提高12%。
相关热词搜索:
上一篇:WSN中一种基于身份的短签名广播认证协议
下一篇:基于粗糙集的入侵检测方法研究