`
lt200819
  • 浏览: 187443 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

海量数据处理之二:Bloom Filter

 
阅读更多

【什么是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亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。
转自:http://blog.csdn.net/hit_kongquan/article/details/6255693
分享到:
评论

相关推荐

    基于Bloom Filter的海量数据分布式快速匹配算法研究.pdf

    3. 分布式技术与Bloom Filter结合:在海量数据快速匹配的背景下,分布式技术可以有效提升处理速度和数据的并发处理能力。文章提出了一种基于Bloom Filter的分布式快速匹配算法,该方法能显著降低程序对服务器内存的...

    海量数据去重的Hash与BloomFilter,bitmap1

    在IT领域,尤其是在大数据处理和分布式系统中,数据去重是一项关键任务。本文将深入探讨两种常用的技术:哈希和布隆过滤器,以及它们在处理海量数据时的应用。 哈希算法是数据去重的基础,它能够将任意大小的数据...

    海量数据处理方法

    海量数据处理是指基于海量数据上的存储、处理、操作,解决方案包括巧妙的算法搭配适合的数据结构,如 Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie 树,以及大而化小、分而治之的策略。根据数据处理的场景,...

    海量数据处理总结(大量数据处理)

    本文将围绕“海量数据处理”这一主题,详细探讨几种核心的技术方法,包括Bloom Filter、Hashing以及Bit-Map,它们在实际场景中的应用以及优化策略。 #### 一、Bloom Filter:高效的空间换时间 Bloom Filter是一种...

    常用大数据量,海量数据处理方法,算法总结

    本文总结了常用的海量数据处理方法,包括 Bloom filter、Hashing 和 bit-map 等。这些方法可以用来解决大数据量的问题,例如数据字典、判重、集合求交集等问题。 Bloom Filter Bloom filter 是一种空间效率高、...

    BloomFilter算法

    在处理大量数据时,如C#中的海量数据,Bloom Filter是极具价值的工具。 **工作原理** Bloom Filter由一个很长的二进制向量和几个不同的哈希函数组成。当一个元素添加到过滤器中时,每个哈希函数都会将元素映射到...

    Java版本的BloomFilter (布隆过滤器)

    总的来说,Bloom Filter是一种巧妙的数据结构,它通过牺牲一定的准确性换取了高效的空间利用和查询速度,特别适用于存储海量数据的场景。在Java开发中,Guava库提供了便捷的接口和优化的实现,使得开发者可以轻松地...

    大数据 海量数据 处理方法总结

    大数据量,海量数据 处理方法总结 包括Bloom filter 哈希 bit-map 堆 双层桶划分 数据库索引 倒排索引 外排序 trie树等。细分为适用范围、要点、实例等。

    海量数据处理的方法

    ### 海量数据处理的方法详解 #### 一、Bloom Filter **定义**: Bloom Filter是一种高效的数据结构,用于快速判断一个元素是否在一个集合中。它使用位数组和多个哈希函数来实现。虽然Bloom Filter可能会产生误报...

    海量数据处理

    #### 二、海量数据处理的核心方法 根据给出的文件内容,我们可以将海量数据处理的关键技术归纳为以下几种: 1. **分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序** - **分而治之/hash映射**:将大数据集分割成...

    教你如何迅速秒杀掉:99%的海量数据处理面试题

    【海量数据处理面试题解析】 在信息技术领域,海量数据处理是一项关键能力,尤其在大数据时代,如何高效地处理和分析海量数据成为企业竞争的核心。本文将深入探讨如何应对99%的海量数据处理面试题,提炼出核心策略...

    大数据量,海量数据处理方法总结[转][文].pdf

    【大数据量,海量数据处理方法总结】 大数据量的处理是现代信息技术领域的重要课题,尤其在互联网巨头如百度、谷歌和腾讯等公司中,这类问题尤为常见。本文将概述几种处理海量数据的有效方法,包括Bloom Filter、...

    99%的海量数据处理面试题

    【海量数据处理】是指在面对数据量巨大,超出单机处理能力的情况下,所采用的一系列技术和方法。这类问题通常涉及到存储、处理和操作大量数据,其中“海量”意味着数据量过大,以至于无法在短时间内直接处理或者无法...

    大数据量,海量数据 处理方法总结

    ### 大数据量,海量数据处理方法总结 在IT领域,特别是大数据分析、数据库管理和算法设计方面,处理海量数据的能力是至关重要的技能之一。本文旨在总结处理大数据量、海量数据的有效方法,涵盖从理论基础到实际应用...

    大数据量,海量数据_处理方法总结

    ### 大数据量、海量数据处理方法总结 #### 一、引言 随着互联网技术的发展,数据量呈现出爆炸性增长的趋势。如何高效地处理这些大数据成为了一项挑战性的任务。在IT行业,尤其是在搜索引擎、社交媒体等领域,处理...

    大数据杀手锏:揭秘 C++ 中 BitSet 与 BloomFilter 的神奇性能!

    《 C++ 修炼全景指南:十四 》大数据杀手锏:揭秘 C++ 中 BitSet 与 ...最后,博客还涵盖了它们在海量数据处理中的实际应用及面试中常见的相关问题,帮助开发者在大数据和分布式系统中合理使用这些工具,提升系统效率。

    常用大数据量、海量数据处理方法__算法总结.pdf

    大数据与海量数据处理算法总结 在当今数据爆炸的时代,大数据处理是IT行业的一个热点。无论是社交网络、电子商务还是搜索引擎公司,都面临着海量数据的存储、查询和分析问题。为了有效应对这些挑战,研究者们提出了...

Global site tag (gtag.js) - Google Analytics