Chinaunix首页 | 论坛 | 博客
  • 博客访问: 40554
  • 博文数量: 9
  • 博客积分: 1557
  • 博客等级: 上尉
  • 技术积分: 124
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-06 17:06
文章分类
文章存档

2011年(2)

2010年(7)

我的朋友

分类: LINUX

2010-12-13 10:39:18

Bloom Filter学习
概述
    当对一个元素x进行判断是否属于集合S时,我们常利用的是hash算法。hash查询虽然非常有价值,但是hash算法对空间的利用率基本为50%,因此当对海量数据进行处理、或者keys自身非常大时,这种利用hash算法的查询方式便变得不实用。Bloom Filter 是对hash函数的一种改进,是空间效率极高的基于随机数的一种数据结构。利用Bloom Filter 可以让你在有限的空间里完成对成员的测试,这个特性将对与海量数据的处理具有极大的吸引力,但是Bloom Filter的这种空间的节省也是有一定代价的,那就是存在着一定的假命中,即误判的风险,并且这种风险根据集合元素的数量,hash函数的选择以及bloom filter空间的大小有密切的关系。因此,此数据结构不适用于“零错误”的场景。由于bloom filter利用了极小的错误率带来了极大的空间利用率,所以bloom filter被被广泛应用于分布式数据库,网络缓存,对等网络,信息检索等领域。

Bloom Filter 原理
    Bloom FIlter 基本思想是利用了多个相互独立的hash函数来对元素的存在与否进行查询,该结构主要包含两部分:k个相互独立的hash函数和一个包含m位的位向量。假设初始集合为具有n个元素的集合S={x1, x2,...,xn},并且Bloom Filter初始是一个包含m位的位向量,每一位均置为0。Bloom Filter使用k个相互独立的hash函数{h1,h2,...,hk},这些hash函数将集合S中的元素映射到{0,1,...,m-1}范围中。对于每一个元素x属于S,则将位向量中对应的h1(x),h2(x),...,hk(x)相应位置为1。之后,当判断元素w的归属性时,就可以通过位向量中h1(w),h2(w),...,hk(w)对应的位全为1来表示元素w属于集合S,如果某一位或则多位存储单元为0,则表示元素w不属于集合S。

错误估计
    正如你想的那样,如果元素w不属于集合S,然而恰好在集合中存在某些元素将w对应的位向量中h1(w),h2(w),...,hk(w)对应位全只为了1,这就产生了“假命中”。假命中率依赖与位向量的长度m,集合元素n的数量。而且如果hash函数选择不好,hash函数产生的热点(即hash值频繁的分布在某些位上)也会增加假命中率。
    在估计之前为了简化模型,我们假设kn
总结
    Bloom Filter在元素的查找过程中利用了多个hash函数进行判定,带有一定的时间换空间性质,但是其在解决问题的同时又引入了误判的问题。但是,在合理选定高质量hash函数以及设计合理的位向量大小后,假命中率会非常的低。由于Bloom filters 非常的简洁,因而其倍受重视。同时,由于Bloom Filter使用hash来存储数据,因此不可能在不做穷举搜索的情况下重建集合S中的元素,所以,Bloom Filter能在不向全世界广播列表的情况下共享已有的资料信息,因此,它们在p2p应用中将非常有用。伴随着网络的普及和发展,Bloom Filter在网络领域获得了新生,各种Bloom Filter变种和新的应用不断出现,Bloom Filter必将获得更大的发展。


reference:
    [1] http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx
    [2] 使用 Bloom Filters   原作者:Maciej Ceglowski  译者:兰花仙子
    [3] Bloom Filters的研究和应用 池净,方启泉
    
阅读(1546) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~