典型bloom过滤器的研究及其数据流应用

《典型bloom过滤器的研究及其数据流应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第35卷第7期计算机工程2009年4月Vol.35No.7ComputerEngineeringApril2009·博士论文·文章编号：1000—3428(2009)07—0005—03文献标识码：A中图分类号：TP311.13典型Bloom过滤器的研究及其数据流应用袁志坚，陈颖文，缪嘉嘉，贾焰，杨树强(国防科技大学计算机学院，长沙410073)摘要：Bloom过滤器是一种空间高效但有一定假阳性的数据表示方法。该文分析比较计数型Bloom过滤器、光谱Bloom过滤器和动态计数过滤器的异同点及适用场合，介绍Bloom过滤器在重复项检测及频繁项挖掘中的应用，总结Bl

2、oom过滤器给数据流带来的挑战，包括元素突发问题及数据流相异元素数目变化问题。关键词：Bloom过滤器；计数型Bloom过滤器；光谱Bloom过滤器；动态计数过滤器；数据流ResearchonTypicalBloomFiltersandTheirDataStreamApplicationsYUANZhi-jian,CHENYing-wen,MIAOJia-jia,JIAYan,YANGShu-qiang(CollegeofComputer,NationalUniversityofDefenseTechnology,Changsha410073)【Abstract

3、】BloomFilter(BF)isaspace-efficientrandomizeddatastructureforrepresentingdatasetwithasmallfalsepositiveprobability.ThispapercomparesandanalyzesthesimilaritiesanddifferencesamongCountingBloomFilter(CBF),SpectralBloomFilter(SBF)andDynamicCountingFilter(DCF),givessomeexamplesandapplicati

4、onsindatastreamwhichincludeduplicateitemsdetectingandfrequentitemsmining.ItsummarizesthechallengesindatastreambroughtbyBF,includingelementburstproblemandnumberofdistinguishelementchangingproblem.【Keywords】BloomFilter(BF);CountingBloomFilter(CBF);SpectralBloomFilter(SBF);DynamicCounti

5、ngFilter(DCF);datastream[1]Bloom过滤器(BloomFilter,BF)采用位数组表示数据1.2假阳性分析集合并有效支持集合元素的成员查询，由于其能显著节省存假设kn

6、景也推动了BloomFilter成员查询时的假阳性f为kk−n/mk理论的发展，产生了计数型Bloom过滤器(CountingBloomfp=−≈−(1)(1e)(2)Filter,CBF)[2]、光谱Bloom过滤器(SpectralBloomFilter,对f取对数，记gfk==−lnln(1e−knm/)，对g取k的导[3][4]SBF)和动态计数过滤器(DynamicCountingFilter,DCF)等数得到多种BloomFilter。∂g=⇒0lk=⋅n2(m/n)optimize1标准BloomFilter∂k(3)1.1BF简介把式(3)代入式

7、(2)，可得设集合Sxxx={,,,L}有n个元素，标准BloomFilter使12nkm/nf=≈(1/2)(0.6185)(4)min用m位的数组BF表示集合S。在初始化时，BF的每位都置为0。设m=cn，如c=8，则f≈2.14%；如c=16，则f≈0.05%。BloomFilter使用k个独立的哈希函数hh,,,Lh，其值域范围12k2计数型BloomFilter为{1,2,L,m}。在添加元素时，对于每个x∈S，2.1CBF简介BFi=1,1≤≤k。对元素y进行集合S的成员查询时，查看hxi()标准BloomFilter不支持从集合中删除元素，如果删除

8、BFihyi(),1≤≤