标记多重嵌套Bloom Filter算法  

Signed multinest Bloom Filter algorithm

作　　者：宋志刚[1] 

机构地区：[1]福州大学网络与信息中心,福建福州350002

出　　处：《闽江学院学报》2008年第2期57-63,共7页Journal of Minjiang University

基　　金：福建省教育厅科技资助项目(JA07025)

摘　　要：Bloom Filter算法是一种高效多哈希算法,它使用紧凑的数据结构以极小且可控的误差率表达一个数据集合,支持查询特定元素是否在集合中出现文中.基于Bloom Filter,针对元素出现频率呈重尾分布的特定集合,提出一种标记多重嵌套Bloom Filter(SMNBF)算法,采用带标记的多重嵌套方式存储集合中元素出现频率的信息.通过对算法的时间和空间复杂度以及误差比例的分析,结果显示该算法以较小计算代价和误差率,大幅减小计算所需的存储空间.将SMNBF算法应用于频率服从重尾分布的集合的实验结果表明,该算法在基本不改变计算误差的基础上,性能明显优于其他类似算法.Bloom Filter is an efficient multi-hash algorithm which uses a space - efficient randomized data structure to represent a set with certain allowable errors, and allows membership queries over this set. Aiming at the set whose items frequencies following heavy-tailed distribution, this paper presents a novel algorithm called Signed Multinest Bloom Filter （SMNBF） based on Bloom Filter. This algorithm applies multinest data structure with a singal to store the items frequency information in the set. The time and space complexities analysis of this algorithm illustrates that it can reduce the space needed dramatically with the cost of little additional CPU-time. And the following experiment indicates this algorithm is more efficient than other algorithms with few errors when the items frequencies of the target set follow heavytailed distribution.

关 键 词：重尾分布 BLOOM FILTER 计数 算法 

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