针对动态集的矩阵型Bloomfilter表示与查找

1、针对动态集的矩阵型Bloom示与查找MatrixBloomfilterondynamicsetXIAOMingzhong,WANGJiacong,MINBonan(NetworkingLaboratory,SchoolofElectronicEngineering&ComputerScience,PekingUniversity,Beijing100871,China):ThispaperpresentedmatrixBloomfilter(MBF),whichusedasXmbitmatrixfordatarepresentandqueryparedtoSBFandDBF,itmoreacc

2、uratelyrepresentedtheessentialcharacteristicsofBloomfilterforitsconstantquerytime.0引言表示和查找信息是大多数计算机应用程序的核心，这两个过程是密切相关的。例如，采用顺序表表示信息则可以使用折半查找；采用哈希表组织信息则可以使用哈希查找。表示就是以计算机能处理的方式把信息组织成为可计算的实体；查找就是确定一个具有特定值的元素是不是一个特定集合的？厂稍？1OBloomfilter使用一个位串对数据集合进行哈希表示与查找，其基本精髓体现在压缩表示和常数查找开销，近年来在大规模分布式系统中得到了广泛应用2。如图1所示的

3、P2P文件共每个对等用户都有很多的文件要共享，在节点之间互相传递共享的文件元数据信息将会消耗掉大量的时间和带宽。利用Bloomfilter，每个节点都可以将它所拥有的资源表示成一个位串，然后再将这些位串发送给附近的超级节点。这样，每个超级节点就收集有附近节点的共享信息。假设节点P5想要查找在对等网络中哪个节点上的文件f,它首先将这个请求发送给超级节点2。超级节点2在自己所收集的Bloomfilter串集合中进行查找，如果在超级节点2没有找到文件f，这个查询请求就会被以flooding方式转发给其他所有超级节点处理，直到查询包TTL值为零或是在某个超级节点找到目标文件f的位置。Bloomfilt

4、er的主要改进型包括压缩型Bloomfilter3计数型Bloomfilter4、空间码Bloomfilter5以及光谱型Bloomfilter6，所有这些表示与查找算法都是针对静态集合设计。然而在实际的应用系统中，只有很少的系统使用静态集，绝大多数的应用处理的是动态数据集合。动态型Bloomfilter（DBF）7和拆分型Bloomfilter（SBF）8可以支持动态集合的表示和查找，但是它们均违背了Bloomfilter查找常数开销的基本精髓。1）相关工作（1）Bloomfilter9Bloomfilter使用长为m的位串V表达数据集合A=a1,a2,an。在初始的时候，位串的所有位都是0

5、。设有k个具有均匀分布特性的哈希函数h1,h2,hk,且xGA,hi(x)1,2,m。对每一个集合A中的元素x,利用k个哈希函数将位串的第hi(x)位置为1。最后，数据集合A被压缩表示成一个Bloomfilter位串。查找某个元素是否属于该集合时，只需使用这些哈希函数作用该元素，查看位串相应的位是否为1即可。上述表示法由于哈希函数的冲突性，会导致某个元数不属于集合A,而被误称属于的可能性，简称误称率。假设hash函数是均匀随机分布的，一个元素被误称的概率可作如下定义：令p表示位串中的某位在对n个集合元素表示结束时仍为0的概率，显然p=(1-1/m)nke-nk/m。式(1)中的PerrBF(m

6、,k,n)就是表示算法的误称率。PerrBF(m,k,n)=(1-p)k勺(1-e-kn/m)k(1)(2)动态型BloomfilterDBF的基本思想是把一个动态集合A表示成一个sXm的位矩阵，这个位矩阵是由s个标准的Bloomfilter位串组成。s的初始值为1，但是它可以随着集合元素的持续增长而不断增大，如图2所示。在初始化时，s被设置成1，所以Bloomfilter1就是当前Bloomfilter位串。在每次向Bloomfilter位串中加入元素时，检查当前的活跃Bloom filter 位串中的元素是否达到了设定的上限值n0o如果没有，就把元素表示到当前活跃的Bloomfilter位

7、串中。如果达到了上限值，则首先把当前的活跃Bloomfilter位串设置成不活跃，然后创建一个新的Bloomfilter位串来作为当前的活跃Bloomfilter位串，把s的值加1。然后用同样的方法把元素表示到当前的活跃Bloomfilter位串中。易知，DBF中只有最后一个Bloomfilter位串永远是活跃的，这意味着它的元素个数没有达到n0,且它之前的所有Bloomfilter位串都被设置成不活跃。(3)拆分型BloomfilterSBF使用不变的sXm的位矩阵来表示一个集合。这里s是一个常量，必须按照对集合尺寸的最大值的估计预先确定好。这种估计可能是基于集合尺寸增长的历史记录或者其他的

8、一些因素，其工作原理如图3所示。在每次添加表示元素前，随机选择一个Bloomfilter位串，然后按照传统Bloomfilter算法进行表示。假设所选择方法是完美随机的，则所有的Bloomfilter位串中表示的元素个数都应该是相同的，其值为n/s。本文用传统的Bloomfilter和MB眯表示同一个动态集合A。对于彳统的Bloomfilter,误称率可以被如下计算：PerrBF(m,n,k)=(1-e-kn/ms)k在MB叶，误称率为PerrMBF(m,n,k)=1-(1-(e-kn/ms)k)s在MBFW专统的Bloomfilter中用到的哈希函数的个数设定为5,MBF中的行误称率与传统的

9、Bloomfilter相同。比较结果如图5所示。从图5中可以看到，为了表示同一个动态集合A,MB阿以获得更好的误称率；并且，MBF的行数越多，误称率越低。同时,相比于传统的Bloomfilter,MB何以更好地支持集合大小n的增长。诚然，MBF#用s倍的空间开销。下面将把MB应用在一个流行的P2P文件共享应用Maze系统10中。内容控制是Maze系统的一项重要功能，用于实现系统范围内非法共享内容的过滤。中心服务器维持着一个被禁止共享文件的列表，每一个用户在登入系统时会从中心服务器获得这个禁止列表。禁止列表是一个动态集合，可能有成千上万项，每一项包含有被禁止文件的属性，如MD5、文件大小等。从中

10、心服务器发送这个禁止列表到各个用户会花费掉很多时间和带宽，并且，维护这个巨大的禁止列表也会占用很多空间。因此，使用Bloomfilter会使情况好很多。在接下来的实验中把禁止列表表示成一个MBF然后同未使用MBF寸比较系统的性能。首先需要确定MBF中每一行的长度m在这个实验中会使用至U五个MBFm=2n,m=3n,m=5n,m=10n以及m=30n。在MBFp所使用到的哈希函数的个数为5，设定的最大误称率为10-4。带宽的消耗如图6所示。用户向中心服务器请求禁止列表时的延迟情况如图7所示。这里的延迟是指，从用户向服务器发出请求，直到该用户得到禁止列表的总的时间。比起直接交换原始禁止共享列表来说，MBFW以很好地节省带宽消耗和缩小获取列表的延迟。3结束语Bloomfilter使用一个位串对静态数据集合进行压缩表示并支持哈希查找操作，近年来在大规模P2P系统中得到了广泛应用。DB林口SB