Bloom Filter技术及应用.pdfVIP

第31卷第3期　 　 　 　 　 　 　 　 　 　 　 阜阳师范学院学报(自然科学版)　 　 　 　 　 　 　 　 　 　 　 　 　 　 Vol.31,No.3 2014年9月 　 　 　 　 　 　 　 　 　 Journal of Fuyang Teachers College (Natural Science)　 　 　 　 　 　 　 　 　 　 　 Sep. 2014 Bloom Filter技术及应用 1 2 1 张　 华 ,郑世珏 ,童德茂 (1.阜阳职业技术学院工程科技学院,安徽 阜阳　 236031;2.华中师范大学 计算机科学系,湖北 武汉　 430079) 摘　 要:Bloom Filter采用位串向量表示数据集合,能够实现高效集合查询的数据结构。 首先介绍了标准布隆过滤器 的概念和工作原理,然后通过实验分析布隆过滤器的错误率、空间向量和哈希函数数量三者之间的动态相关关系,并对独 立空间布隆过滤器和标准布隆过滤器性能进行对比,最后讨论了Bloom Filter 的变种及应用。 关键词:Bloom Filter;错误率;标准布隆过滤器;独立空间布隆过滤器 中图分类号:TP301　 　 　 文献标识码:A　 　 　 文章编号:1004-4329(2014)03-062-05 Bloom Filter technology and its applications 1 2 1 ZHANG Hua ,ZHENG Shi-jue ,TONG De-mao (1. Institute of Engineering and Technology,Fuyang Vocational and Technical College,FuyangAnhui236031,China; 2.Department of Computer Science,Huazhong Normal University,WuhanHubei430079,China) Abstract:Bloom Filter is a data structure that uses bit string vector to represent data set so asto meet efficient membership queries. First,the concept andtheoperatingprincipleof standardBloomFilterweregiven. Second,basedonexperiments,thedy- namic relationships amongthefalsepositive,thevector spaceandthenumbersof hashfunctionof BloomFilterwereanalyzed. Fur- thermore,the performance of independence space Bloom Filter and that of standard Bloom Filter were compared. Finally,applica- tions and development of Bloom Filter were discussed. Key words:Bloom Filter;false positive;standard Bloom Filter;independence space Bloom Filter 　 　 Bloom Filter是由Burton Bloom提出的采用位 编码后的位数比集合元素位数少,因此节省了存储 串向量表示数据集合,能够实现高效集合查询的数 空间。 编码位数取决于你所期望的错误率,编码位 [1] 据结构 。 它是以哈希表为基础的算法。 哈希表 数越多,错误就越少,反之则越大,即“正确率换取 的基本原理是使用一个容量相对合适的数组来保 空间”的思想。 布隆过滤器就在这一思想下产生。 存数据,在记录的存储位