因为要交个作业,因此陆续会写一些关于Bloom filter的东西。
Bloom filter 由Burton Bloom于1970年提出,它用一个m个bit长的位向量V来表示一个集合S{s1,s2,...sn},首先向量V初始化为0。Bloom Filter用K个哈希函数h1,h2,...hk将来自S集合的元素映射到位向量的h1(s),h2(s),...,hk(s)位置上设为1。对于任意一个,判断q是否是S的成员可以通过:检查h1(q),h2(q),...hk(q)是否为1进行判断。如果不全为1,则q必然不是S的成员。但如果全为1,可能会出现假阳性错误(false positive error),这是由于其他成员将这些位置都置1造成的,这个错误我们定义为Eb。
因此可得结论:n个元素,每个元素占k个bit,m个bit长度的vector,r = ln(2)=0.7时,布隆过滤器的错误率最低。
该结论可用于已知2个变量估算另外一个变量的取值,例如已知集合元素个数和哈希函数个数,估计需要多少bit来表示位向量最佳等等。另外0.6185这个数值多么像黄金分割率啊,让人砰然心动,可惜差一点点。
本文参考部分文献
(1)Spectral Bloom Filters Sarr Cohen,Yossi Matias SIGMOD 2003
(2)http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx
(3)http://www.google.com.hk/ggblog/googlechinablog/2007/07/bloom-filter_7469.html
分享到:
相关推荐
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不...
bloomfilter.js, 使用FNV的JavaScript bloom filter快速散列 Bloom过滤器This过滤器实现使用非加密 Fowler-Noll-Vo散列函数来实现速度。用法var bloom = new BloomFilter( 32 * 256,//number of bits to all
Bloom filter是一个简明的空间效率极高的随机的数据结构。用Bloom filter 表示 cache 内容 ,可以高效地实现cache 协作。本文对BloomFilter及其改进型进行了综述性分析,探讨了它的实用性。
分布式环境下改进的BloomFilter过滤技术
This is the bloom filter of 2.5 Million ... BloomFilter bf=new BloomFilter(); BitSet bitSet=bf.readBit(fileName); bf.setBits(bitSet); System.out.println(bf.exist("password")); } it will says true.
leveldb中bloomfilter的优化。
Respect! The original paper about bloom filter. Very beginning of hash error tolerate algorithm to get wanted data faster.
相似项发现主题中的shingling、simhash、bloom filter算法java实现,测试通过,附带测试数据。
bloom filter(布隆过滤器)应用很广泛的高效算法,研究研究
bloom-filter-scala, 用于 Scala的Bloom过滤器,最快的JVM Scala的 Bloom filter 概述Bloom过滤器是一种空间高效的数据结构,用于测试某个元素是否是集合的成员。 false 正匹配是可能的,但 false 负数不是。 ...
bloom filter的一些论文 有综述,有应用,较为详细 不过可能需要下载cnki的阅读器,这个比较好下,大家可以自己下个
这是一个java版的bloomFilter Hash函数集,并带有测试程序。在我的资源里还有一个c版的,函数功能相同,在我的应用中具有良好表现。
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
提出一种针对动态集合的矩阵型Bloom filter表示与查找法(matrix Bloom filter,MBF),它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。
基于bloomfilter的大规模网页去重,判断是否爬过URL
linux下编写的网络爬虫,可以实现bloom filter 去重过滤,不过是用来垂直爬取www.8684.cn网站的。运行的时候请输入www.8684.cn
C# 海量数据处理算法BloomFilter算法的实现和测试例子;C# 海量数据处理算法BloomFilter算法的实现和测试例子
Java-BloomFilter, 在Java中,一个独立的Bloom过滤器 java-bloomfilterJava bloomfilter是一个独立于Java的Bloom过滤器实现。 它旨在在不需要额外库开销的情况下包含在现有项目中。 第一个版本是由 Ian的博客条目...
该文档中包含 bloomFilter过滤器中用到的对于字符串进行hash的hash函数共十一个,并带有测试程序..
open bloom filter是我见过的bloom filter之中写的比较好的一个,但是其中的数值范围过大,获取hash函数时测试次数过多。希望对你有所裨益,使用的时候请遵守原作者的权益。见过csdn上好多不要脸的人,别人写的东西...