来自:http://blog.redfox66.com/post/2010/09/24/mass-data-topic-2-bloom-filter.aspx
【什么是Bloom Filter】
Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍,不太懂的博友可以看看。
【适用范围】
可以用来实现数据字典,进行数据的判重,或者集合求交集
【基本原理及要点】
对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
还有一个比较重要的问题,如 何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况 下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
【扩展】
Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
【问题实例】
给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?
根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿bit,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。
分享到:
相关推荐
《 C++ 修炼全景指南:十四 》大数据杀手锏:揭秘 C++ 中 BitSet 与 ...最后,博客还涵盖了它们在海量数据处理中的实际应用及面试中常见的相关问题,帮助开发者在大数据和分布式系统中合理使用这些工具,提升系统效率。
以上技术在大数据场景下尤其重要,它们能够在有限的内存资源下处理海量数据,提供高效且节省空间的解决方案。理解和熟练运用这些数据结构和算法是IT专业人员必备的技能。在实际应用中,可以根据具体需求和资源限制...
大数据处理在当今信息化社会中扮演着至关重要的角色,它涉及海量数据的收集、存储、管理和分析,以揭示潜在的业务洞察和模式。然而,随着数据量的爆炸性增长,如何提高大数据处理的效率成为了业界关注的重点。"大...
《HBase上搭建广告实时数据处理平台——广点通》 在互联网广告行业中,实时数据处理平台对于广告的精准投放至关重要。腾讯广点通作为基于腾讯社交体系的效果广告平台,其WRAPENGINE项目旨在构建一个高效、可靠的...
"SQL数据库对于海量数据面试题及答案" 本文整理和大家分享一些SQL 数据库对于海量数据面试题及答案给大家,很不错哦,喜欢请收藏一下。 问题 1:找出 a、b 两个文件共同的url 给定 a、b 两个文件,各存放50 亿个 ...
### Google、Baidu、Tencent 面试题总结——海量数据处理方法 #### Bloom Filter **适用范围**:Bloom Filter是一种空间效率极高的概率型数据结构,主要用于判断一个元素是否在一个集合中。它适用于数据字典的实现...
hyperfilter的工作原理可以简单理解为一种布隆过滤器(Bloom Filter)的变体。布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。尽管可能会有误判,但在处理海量数据时,其...
BitMap和Bloom Filter是解决大型数据问题的有效方法,包括BitMap的基本思想、BitMap应用之快速排序、快速去重、快速查询、BitMap扩展——Bloom Filter等。 十三、限流算法 限流算法包括计数器法、滑动窗口、漏桶...
在这个"数据结构与算法分析JAVA_LAB06"实验中,我们聚焦于一个特殊的概率数据结构——布隆过滤器(Bloom Filter)。 布隆过滤器是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。它可能会...
然而,这种特性在处理海量数据时,可以极大地减少存储需求和查询时间,特别适用于在网络环境中快速查找是否存在特定元素。 论文还讨论了布隆过滤器的改进算法,旨在降低误报率,提高IDS的准确性和效率。通过将IDS与...
3. **索引优化**:Tera引入了Bloom Filter和Index Tablet等技术,减少了不必要的磁盘I/O,提高了查询效率。 4. **数据压缩**:为了减少存储空间,Tera支持数据压缩,如LZ4和Snappy压缩算法,降低了存储成本。 5. *...
例如,可以通过`io.seqfile.compress.blocksize`来设置SequenceFile的压缩块大小,或者通过`io.mapfile.bloom.size`控制Bloom Filter的大小,以优化性能。此外,对于MapReduce作业,可以考虑是否在map阶段就进行压缩...
在大数据领域,HBase作为一种分布式、列式存储的NoSQL数据库,因其高效处理海量数据的能力而备受青睐。本篇将深入探讨HBase在GIS(地理信息系统)领域的应用实例,即GISMaster项目,以此来揭示HBase在处理空间数据上...
《快速搜索近似最近邻——探索fastAnn的高效算法与应用》 在计算机科学和机器学习领域,近似最近邻(Approximate Nearest Neighbor, ...在面对海量数据时,fastAnn的快速搜索近似最近邻能力无疑是我们不可或缺的助手。
在大数据处理中,搜索引擎是不可或缺的一部分,用于快速检索海量数据中的特定信息。Python 作为一门易读、易学且功能强大的编程语言,非常适合用来构建这样的系统。本篇内容将介绍如何利用 Python 实现一个基本的...
为了克服这些限制,提出了一种新型的索引结构——CBFM(Cutted Bloom Filter Matrix),即支持属性删减的布鲁姆过滤器矩阵。CBFM的核心优势在于能够通过独立属性布鲁姆过滤器的笛卡尔乘积构建位矩阵,这种结构支持...