联合多维布鲁姆过滤器查询算法.doc

第1期谢鲲等：联合多维布鲁姆过滤器查询算法65联合多维布鲁姆过滤器查询算法谢鲲1,4，秦拯2，文吉刚1，张大方2，谢高岗31(1. 湖南大学 计算机与通信学院, 湖南 长沙 410082; 2. 湖南大学 软件学院, 湖南 长沙 410082;3. 中国科学院 计算技术研究所 网络与普适计算研究部, 北京100080; 香港理工大学 电子计算学系，香港 九龙红石勘)摘 要：分析了现有多维布鲁姆过滤器查询算法(MDBF)工作原理，提出了一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF)查询算法。CMDBF新增一个用于表示元素整体的联合布鲁姆过滤器CBF，CMDBF中元素表示和查找分两步进行。将MDBF的各属性的表示和查询作为第一步，第二步联合元素所有属性域，利用CBF完成元素整体的表示和查询确认。理论分析和仿真实验结果表明，CMDBF能够支持多维集合元素的简洁表示和查询，相比MDBF查询误判率降低明显。关键词：计算机网络；分布式计算；分布式消息系统；集合元素查询；多维布鲁姆过滤器中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)01-0056-09Combine multi-dimension Bloom filter for membership queriesXIE Kun1,4, QIN Zheng2, WEN Ji-gang1, ZHANG Da-fang2, XIE Gao-gang3(1. School of Computer and Communication, Hunan University, Changsha 410082, China;2. School of Software, Hunan University, Changsha 410082, China;3. Networking and Ubiquitous Computing Department, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, China;4. Department of Computing, The Hong Kong Polytechnic University, HungHom Kowloon, China)Abstract: Based on the analysis of multi-dimension Bloom filter(MDBF) presented before, a combine multi-dimension Bloom filter(CMBE) was presented. CMDBF adds a combine Bloom filter (CBF) to MDBF to assist in representing the whole element. When representing or querying an element, CMDBF needs two steps, the first step is representing or querying every attribute of the element with MDBF, the second step is combining all attributes to further represent or query the whole element with combine Bloom filter for further validation. Both theoretical analysis and experiment show that the CMDBF can support concise representation and approximate membership query of data set from multiple attribute dimensions and CMDBF outperforms MDBF in false positive.Key words: computer networks; distributed computing; distributed information system; set membership query; multidimensional bloom filter1 引言收稿日期：2006-12-07；修回日期：2007-10-11基金项目：国家自然科学基金资助项目(60673155, 90604015, 60703097); 湖南省科技计划基金资助项目(2006FJ4110)；广东省科技计划基金资助项目(2007B01020043)Foundation Items: The National Natural Science Foundation of China(60673155, 90604015, 60703097); The Science and Technology Plan of Hunan Province(2006FJ4110); The Science and Technology Plan of Guangdong Province (2007B01020043)布鲁姆过滤器(Bloom filter)是一种精简的信息表示方案。布鲁姆过滤器对集合采用一个位串向量表示并能有效支持元素的哈希散列查找，是一种能够表示集合、支持集合查询的简洁数据结构。与传统查询算法、结构相比，传统的树型查询算法和哈希散列查询算法存储空间与元素自身大小和集合规模直接相关，而布鲁过滤器查询算法所需空间与元素自身大小无关，仅与元素映射到向量位数相关，大大节约存储空间。布鲁姆过滤器查询算法虽然存在稍许查询误判1,2，但是由于其哈希散列查找的常数时间和存储空间开销较小，从而使它具有很好的实用价值。最初的应用主要集中在数据库操作、字典查询和文件操作2。最近10年，随着网络研究的发展以及新的覆盖网和P2P网络应用技术的涌现，出现了布鲁姆过滤器查询算法研究高潮，应用于网络的领域和方式越来越多2,3，包括覆盖网和P2P网节点协作交互4,5、资源路由6、数据帧路由标签7、网络测量管理8,9、网络入侵检测(intrusion detection)10、无线网络交互协议设计11、流数据管理12等网络应用领域。随着布鲁姆过滤器查询算法越来越多地被研究人员认识和重视，它将在现代计算机网络和一些新的学术领域得到更为广泛的应用。目前布鲁姆过滤器算法的研究主要集中在单维元素的表示和查询，如标准布鲁姆过滤器算法1、计数器布鲁姆过滤器算法13、压缩布鲁姆过滤器算法14，光谱布鲁姆过滤器算法15、拆分型布鲁姆过滤器查询算法16、动态布鲁姆过滤器算法17和本文作者提出的分档布鲁姆过滤器算法18,19和可扩展布鲁姆过滤器查询算法20。这些算法从不同的角度讨论和优化布鲁姆过滤器的设计以满足实际应用的不同需求。但是，布鲁姆过滤器查询算法研究处于急需发展的阶段，存在很大的理论创新空间2。除了单维元素的表示和查询，在分布式系统中，多维元素的表示和查询是经常遇到的问题。以网络监测管理系统中的网络业务流为例，每个业务流都由五元组(source address, dest address, source port, dest port, protocol)惟一确定，在表示和查询网络业务流这种5维元素集合时，同样需要高效算法提高系统效率。所以，利用布鲁姆过滤器查找方便，空间简洁的特点，研究多维元素的高效查询算法，完成多维元素高效表示和查询成为查询算法领域迫切需要解决的问题，具有广泛的应用前景。针对多维元素的表示和查询存在一种布鲁姆过滤器解决方案，文献17提出多维布鲁姆过滤器(MDBF, multi-dimensional bloom filters)。MDBF由多个标准的布鲁姆过滤器组成，每个标准布鲁姆过滤器用来表示元素的一维属性子集合。MDBF实现简单，但是由于任何一维属性值出现误判，都会导致元素误判，MDBF分割了各属性值合为元素一体的特点，误判率较高，算法具有改进的空间。本文详细讨论了多维元素的布鲁姆过滤器表示和查询方法，分析MDBF算法在元素表示和查询时的缺陷，提出一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF, combine multi- dimensional Bloom filters)。CMDBF在MDBF的基础上，增加一个联合标准布鲁姆过滤器CBF，将多维元素整体经过2次哈希散列运算表示到CBF中。CMDBF的元素表示和查找分2步进行，将MDBF作为元素表示和查找第一步，第二步联合元素各属性值利用CBF进行确认。仿真实验表明，CMDBF和MDBF相比，虽然以增加一个m bit长的向量空间为代价，查询误判率降低效果明显。2 布鲁姆过滤器相关研究2.1 标准布鲁姆过滤器标准布鲁姆过滤器查询算法1，核心是一个V向量和一组哈希散列函数，标准布鲁姆过滤器原理如图1所示。设集合S=s1,s2,sn共有n个元素，通过k个哈希散列函数h1,h2,hk映射到长度为m的向量V中。每一个哈希散列函数相互独立且函数的取值范围为0,1,2,m1。集合映射到过滤器时，向量V初始化，将向量V所有比特位置0。当元素插入集合中时，对于每一个元素si，计算hj(si)(1jk)，若hj(si)=q，则令BFq=1，将向量对应位置置位，完成元素的插入。当查询元素是否在集合时，对于给定的元素x，检查向量V的k个位置(h1(x),h2(x),hk(x)是否都为1。如果有一个为0，x一定不在集合中；如果全是1，x可能在集合中，但不一定。此时就可能出现所谓假阳性误判(false positive)14，将不属于集合的元素误判断成属于集合中，而不存在假阴性误判(false negative)，将属于集合中的元素而误判为不属于集合中。图1 标准布鲁姆过滤器原理例1 图2是标准布鲁姆过滤器查询算法实例。布鲁姆过滤器向量长度m=5bit。每次映射和查找的哈希散列函数的个数为k=2个，2个哈希散列函数分别为h1(x)=x mod 5和h2(x)= (2x+3) mod 5。其中数据集合是S=9,11，需要查询的元素是15和16。图2 标准布鲁姆过滤器查询算法实例定义1 将不属于集合的元素误判断成属于集合中称为一次误判。发生误判的概率称为误判率。下文用三元组n,m,k形式化表示标准布鲁姆过滤器算法，用四元组n,m,k,L表示多维布鲁姆过滤器。n为集合S的元素个数，m为向量V的长度，k为哈希散列函数个数，L为元素维数。在本文的讨论中，假设哈希散列函数取值服从均匀分布，当集合中所有元素都映射完毕后，V向量任一位为0的概率为(1)标准布鲁姆过滤器的误判率为14(2)使用标准布鲁姆过滤器完成集合存储。m比特位的向量表示n个元素的集合，每个元素平均保存m/n位，空间十分节俭。布鲁姆过滤器是在空间节俭和查询误判上的一个折衷。2.2 多维布鲁姆过滤器MDBF针对多维元素的表示和查询问题，目前存在一种多维布鲁姆过滤器(MDBF) 17解决方案。MDBF采用和元素维数相同的多个标准布鲁姆过滤器组成，直接将多维元素的表示和查询分解为单属性值子集合的表示查询，元素的维数有多少，就采用多少个标准的布鲁姆过滤器分别表示各自对应的属性。进行元素查询时，通过判断多维元素的各个属性值是否都在相应的标准布鲁姆过滤器中来判断元素是否属于集合。如图3所示。对于n,m,k,L的MDBF，判断元素是否从属集合，需要判断所有的属性值是否在对应的属性子集合，多维布鲁姆过滤器误判率为17图3 MDBF工作原理(3)多维布鲁姆过滤器查询时间为O(kL)，所需空间为O(mL)。3 联合多维布鲁姆过滤器(CMDBF)3.1 MDBF分析通过一个二维元素表示和查询的例子来分析现有MDBF误判率情况。经过分析指出MDBF算法在元素表示和查询时的缺陷，进而给出改进的CMDBF查询算法。例2 多维布鲁姆过滤器查询算法实例。设二维元素为x=A1,A2，其中A1和A2是2个不同的属性。使用MDBF需要2个标准布鲁姆过滤器BF1、BF2用来分别表示属性A1和属性A2。单属性域的布鲁姆过滤器向量都取m=8 bit。每次映射和查找的哈希散列函数的个数为2个，2个属性值映射的哈希散列函数取一致，简单定义这2个哈希散列函数为：h1(x)=x mod 8和h2(x)=(2x+3) mod 8。其中数据集合是(9,7), (11,9)，需要查询的元素是(11,15)。表示集合之前，2个向量都需要初始化。元素(9,7)插入后，第一维布鲁姆过滤器向量BF11和BF15置位，第二维布鲁姆过滤器向量BF27和BF21置位，两向量状态分别如图4第2行所示。那么元素(11,9)插入后的向量状态如图4第3行所示。图4 MDBF算法实例查询(11,15)是否在集合中。首先检查11是否在第一个属性集合中，11对应的2个哈希散列地址3、1，发现BF13，BF11都已置位，说明11在属性A1集合中。然后检查15的2个哈希散列地址，发现BF27，BF21也已经置位，说明15也在属性A2的集合中，得出(11,15)在集合中的错误结论。文献17提出了MDBF算法，并认为“MDBF出现误判的情况是每维都出现误判断时，元素才会被误判断”。通过上面的实例分析发现：实际上，MDBF算法在任何一维误判断时都会导致元素的误判断。如例2所示，两维元素(11,15)进行查询判断时，第二维15却不在第二维子集中，但是使用BF2误判断15在该子集中，此时就出现了两维元素由于一维的误判而导致元素整体的误判。成为MDBF的缺陷。上述结果的产生，是因为MDBF使用每个单独的BF来表示元素的每个单独的属性值，没有相应的结构将各属性值合成的元素表达出来。MDBF分割了各个属性值属于元素一体的特点，仅通过单独判断元素的各个属性值是否在对应的子集合来进行元素的从属判断，不可避免发生例2的情况，将不属于集合的元素(11,15)误判为属于集合，因此有必要对MDBF进行改进。3.2 联合多维布鲁姆过滤器(CMDBF)原理图5 CMDBF算法实例考虑到如果能将各个属性合为一体的特性在布鲁姆过滤器中表示出来，得到元素的整体信息必然可以减少由于单维属性误判而导致的元素整体误判的可能性。由此提出改进的联合多维布鲁姆过滤器(CMDBF, combine multi-dimensional Bloom filters)。CMDBF由两部分过滤器组成，第一部分是用标准布鲁姆过滤器表示的各属性子集，采用和MDBF一样的机制；第二部分是一个联合布鲁姆过滤器CBF(combine blooms filter)，用来表示各个属性值的联合。这里存在如何将元素表示到CBF的问题，如果MDBF每次映射哈希散列地址范围一致，那么可以直接用不同属性域的对应哈希散列映射地址进行异或运算，通过2次哈希散列运算获得元素在CBF中的位置，将CBF对应位置置位，完成元素到CBF的表示。下面用一个例子来解释算法思路，如图5所示，其中，为异或运算。例3 用CMDBF表示的二维集合(9,7), (11,9)，查询(11,15)是否在集合中。表示集合之前，3个向量都需要初始化。2个元素插入后，BF1和BF2状态和例2中的MDBF完全相同。所不同的是，改进的多维布鲁姆过滤器中，增加了一个联合过滤器CBF，元素(9,7)在CBF的映射地址可由单属性9,7在BF1和BF2中的地址直接计算，如addr1=17=6(这里的1是属性“9”在BF1中的地址，7是属性“7”在BF1中的地址，addr1是由2个属性“9”，“7”共同决定)，addr2=51=4。因此将CBF6和CBF4置位，完成元素(9,7)的插入。同理完成元素(11,9)到CMDBF的表示，状态如图5第3行所示。查询(11,15)是否是集合的元素。在MDBF的基础上，还需要进行元素整体是否在CBF的检查，元素(11,15)在CBF中的2个映射地址分为addr1=37=4，addr2=11=0。虽然CBF4=1，但是CBF0=0，得出元素(11,15)不在集合中的正确结论。虽然CMDBF算法只在MDBF算法上增加了一个用于表示各属性联合的CBF过滤器，但元素在CBF的映射位置由所有的属性值共同决定，有效解决由于单属性的误判断而造成元素整体误判断的可能。设多维元素x=A1,A2,AL，使用布鲁姆过滤器，虽然对于每维属性值，可能需要选择不同的哈希散列函数，但是仍然可以设计每维属性使用相同的哈希散列函数个数ki=k(1iL)，每个属性维数使用相同的长度的过滤器向量mi=m(1iL)。那么每个属性的哈希散列映射地址为(4)和MDBF一样17，attrj_addri0,1,m1就是属性j的第i个哈希散列地址。这就为每维属性值的联合提供了方便，可以通过这些映射地址的运算完成元素的多属性联合表示，可定义联合布鲁姆过滤器CBF的哈希散列函数为(5)addri(1ik)是元素在CBF中的第i个映射地址，由各个属性值的映射地址通过异或运算得来，由多个属性联合确定。可以表现元素各属性值一体的特性，而且异或函数也是常用的哈希散列处理函数。由attrj_addri易得addri，这样定义的CBF向量长度仍然是m。CMDBF在MDBF基础上增加一个联合的布鲁姆过滤器CBF，而新增的CBF又由元素的所有属性值确定，这样元素整体就可以通过2次哈希散列运算表示出来，完成元素的表示和查找，如图6所示。图6 CMDBF算法原理定理1 CMDBF算法的查询误判率小于MDBF算法。证明 对于n,m,k,L的CMDBF，判断元素是否从属集合，需要第一轮MDBF的L个布鲁姆过滤器和第二轮联合布鲁姆过滤器对应位置都已置位。第二轮联合布鲁姆过滤器CBF的误判率可以直接计算为(6)则CMDBF的误判率为(7)由于0f BF(m,k,n)1，由式(3)和式(7)显然有f CMDBf MDBF。推广到更一般的情况，当进行元素到CBF的表示时，如采用其他由attrj_addri到addri的转换方法，此时CBF的长度可能并不是m，设为m1，由式(2)知，0f CBF(m1,k,n)1，式(7)仍然可以得出f CMDB f MDBF的结论。虽然CMDBF采用多于MDBF一个m bit长度的向量空间为代价，但是能够将元素属性值表达成一个整体，可以得到比MDBF更低的查询误判率，在第4节的实验分析中，将得出这种空间消耗对整个算法的性能影响并不大。3.3 联合多维布鲁姆过滤器算法CMDBF算法的元素插入流程如图7所示。新元素加入时，首先分离元素的各个属性值，将每个属性值对应的标准布鲁姆过滤器置位，同时，在计算每个属性值映射地址时，通过异或运算，得到由多属性值确定的该元素在联合布鲁姆过滤器CBF的地址，将对应地址位置位，完成元素的插入。图7 CMDBF算法元素插入进行元素是否在集合的查询判断时。使用CMDBF，需要进行2个步骤的检查，第一轮检查各个单维的属性值是否在单维属性子集合中，如果此轮检查发现元素的各属性值都已经映射到单维布鲁姆过滤器中，再进行第二轮检查，第二轮由各维属性值联合映射所对应的联合布鲁姆过滤器(CBF)是否都被置位，如已经被置位，判断该元素属于集合。CMDBF的元素查询如图8所示。联合多维布鲁姆过滤器查询时间为O(k(L+1)= O(kL)，存储空间为O(m(L+1)=O(mL)。图8 CMDBF算法元素查询4 仿真实验本节通过仿真实验来验证2种多维布鲁姆过滤器算法性能。实验1 通过随机实验验证算法性能。对二、三、四、五维元素集合分别进行实验。为了简化实验，每一维属性值直接采用的32bit整数，这些32bit整数都是由计算机随机产生的32bit的无符号整数，数值范围为0,2321。映射哈希散列函数采用Carter和Wegman定义的H3哈希散列函数21，每个H3哈希散列函数对应一个0,1函数矩阵，H3函数具有很强的散列性，是一种常见的布鲁姆过滤器的实现函数22,23，随机产生H3哈希散列函数矩阵，数据集合中每个元素的各个属性均通过k个哈希散列运算映射到该属性对应的向量中和联合向量CBF中。实验过程首先将10 000个元素通过元素插入流程表示到过滤器中。为了得到查询误判率，采取1 000个不在这10 000个元素集合中的元素完成布鲁姆过滤器查询，进行误判数目统计。如果所需查找元素的所有属性值对应的k个映射位置均为1，表明该元素在集合中，出现了误判，因为这1 000个元素都是不在集合中的元素。统计误判率为累计误判元素的个数和1 000比值。同时，为了得到一般的结论，对于每一组n,m,k,L，使用100个不同的多维数据集合完成100次仿真实验，仿真实验的误判率平均值和标准差如表1所示。为了比较起见，将误判率和空间消耗放到同一个表格中。从表1，可以得出：1）仿真实验的误判率均值和理论结果十分一致，而且每组仿真实验的标准差都较小，不仅验证了误判率理论公式的正确性，而且说明通过随机产生的H3哈希散列函数完成的布鲁姆过滤器表示和查询，函数的散列性好，哈希散列地址可以均匀的分布到布鲁姆过滤器向量中。2）使用相同的哈希散列函数个数，当元素的维数越大时，查询误判率越低，验证了理论的误判率随着元素维数增加时的趋势，如式(3)和式(7)所示。3）当使用相同的哈希散列函数个数时，如L=2，k=4时，CMDBF的误判率为0.015 045，而MDBF的误判率为0.060 47，约为CMDBF的误判率的4倍，CMDBF查询误判率明显低于MDBF的查询误判率。4）当L=5时，CMDBF使用196 608bit表示10 000个元素，平均每个元素占用20bit空间，而如果直接存储五维元素，共需要325=160bit，用CMDBF算法节约空间87.7%。虽然CMDBF比MDBF多一个联合布鲁姆过滤器CBF(m=32 768bit)的空间为代价，(CMDBF的空间消耗依然十分少，具有布鲁姆过滤器算法空间节俭的特点)，但是其查询误判率明显优于MDBF，具有更好的查询算法性能。实验2 根据实际trace记录进行网络业务流主机对统计。为了进一步验证所提出的CMDBF的有效性。本节对实际网络trace数据进行分析，统计实际网络中一段时间内的网络业务流主机对分布情况。实验数据源采用NLANR 的Trace25。实验目的是借助布鲁姆过滤器这种简洁的数据结构，统计每个时间片的通信主机对的个数，获得随时间的通信流量主机对的分布。进而为进一步构建网络OD(origin-destination)流矩阵，为网络测量的全网流量分析和流量预测奠定基础。本实验的工作是统计随时间分布的网络业务流量主机对。从网络数据报文中提取源IP地址和目的IP地址组成的二维元素(Source_IP，Dest_IP)的集合是实验中操作的数据集合。实验中分别使用MDBF和CMDBF算法辅助完成主机对个数统计，进而和实际网络运行结果比较。实验过程如下：Step1 首先初始化BF(实验中分别实现了MDBF和CMDBF 2种算法)，将它们作为存储网络业务流主机对的数据结构；表1MDBF和CMDBF比较n=10 000；m=32 768bit； k=4,6,8；L=2,3,4,5维数哈希散列函数MDBF误判率MDBF空间/bitCMDBF误判率CMDBF空间/bit理论值仿真实验理论值仿真实验均值标准差均值标准差2K=40.06 1010.060 470.002 0665 5360.015 070.015 0450.001 27198 304K=60.122 980.123 6960.003 660.043 1270.043 0580.002 285K=80.232 9380.233 0570.005 3790.112 420.112 990.004 0033K=40.015 070.014 8770.001 25598 3040.003 7220.003 5480.000 612131 072K=60.043 1270.043 3350.001 9520.015 1240.015 2880.001 365K=80.112 420.111 4110.004 170.054 260.053 5320.002 6254K=40.003 7220.003 8270.000 333131 0720.000 9190.000 9490.000 333163 840K=60.015 1240.015 2940.001 2030.005 3040.005 340.000 805K=80.054 260.054 5270.002 9060.026 1880.026 1660.001 85K=40.000 9190.000 9230.000 297163 8400.000 2270.000 2420.000 169196 608K=60.005 3040.005 3390.000 7460.001 860.001 8510.000 425K=80.026 1880.026 2210.001 8580.012 6390.012 640.001 256Step2 从Trace中获得数据报文，对于每一个数据报文，首先查询其对应源IP地址、目的IP地址二维元素(Source_IP，Dest_IP)是否在对应的BF中？Step3 No，表明这是一个新的主机对，将新的二维元素(Source_IP，Dest_IP)插入到对应的BF中，将相应的统计变量加1；Step4 Yes，表明该主机对已经存在，则处理下一个数据报文，转Step2。实验结果如下。实验数据来源是加州大学的圣迭戈超级计算机中心(SDSC)到Abilene的OC12链路，报文格式DAG3.2，采集于2005年8月1日。图9(a)采用标记为SDA-1122856626的Trace数据源，采集时间为上午08:38:14.26734808:39:47.196113；图9(b)采用标记为SDA-1122879035的Trace数据源，采集时间为下午14:51:43.34630514:53:15.616775。2个数据源分别持续93s，进行报文统计的时间粒度t为1s。从图9(a)和图9(b)，可以看出使用CMDBF算法获得的主机对和真实网络流量主机对基本一致，具有很高的准确性，并且比MDBF算法提高精度10%左右。(如果直接采用上面的公式进行理论计算，只可能提高精度4%左右，这里6%的差距是因为IP报文的地址和上述的随机数据源不同，多个元素的单属性值存在一定的相关性，如相同的源地址对应不同目标地址组成的多个元素)。CMDBF算法在此情况下比MDBF算法具有更好的性能；CMDBF的查询误判率永远小于MDBF，尤其是当集合的多维属性和属性值存在一定相关性的情况下，图9 网络业务流主机对分布CMDBF比MDBF查询误判率降低明显。而且由于算法自身的空间简洁，可以有效的在高速缓存中实现，从而加快数据报文处理速度，可直接用于高速网络数据报文处理，具有较强的实用性。5 应用探讨布鲁姆过滤器的一个典型应用是Web代理系统13：用布鲁姆过滤器表示每个代理所缓存的URL目录摘要(summary cache)，并存储到代理的高速缓存DRAM中，代理之间通过互传这种Summary Cache信息来相互告知自己缓存的网页内容，加速网页信息的查找。这类应用中，集合的元素是URL地址，如果假设每个地址约需要50个ASCII码字符，若采用传统的哈希散列精确组织该集合至少需要(4001)n个比特内存空间1,16，而采用布鲁姆过滤器仅需要m个bit的存储空间(实际中m400n)。现在的万维网就是按照“网页的地址”而非“内容的语义”来定位资源，随着语义网(semantic web)的悄然兴起，人们需要按照内容的语义表达需求，迅速准确地从成千上万地网页中得到自己感兴趣地内容，语义网引入资源描述框架RDF24(resource description framework)作为其存放元数据的通用格式和语法结构。RDF下的数据模型是一个三元组，而不再是万维网中网页地址，对于这种新的网络环境下的数据表达的多属性元素的表达和查找，CMDBF又是一种很好的选择。CMDBF在网络监测和网络管理上也有较好的应用。Internet路由器转发过程中，主要有3个瓶颈：查找、交换和输出调度，而当前路由器上的瓶颈主要表现在路由器的查找效率上，近年来兴起的一些网络应用希望路由器能够完成诸如：防火墙、基于策略的路由、区分服务、QoS、流量计费等的功能支持，这类应用中涉及的业务流判别，通常需要查找IP报头的多个域，以此来决定其归属于哪个业务流。此时路由查找表需要从单维的目的地址的查找，转换到支持多维的数据流规则的查找。文献20使用标准的布鲁姆过滤器来辅助设计单维的路由表查找表，随着4层交换、7层交换的发展，使用CMDBF可以辅助我们设计多维业务流的路由查找表。CMDBF还可以用于覆盖网和P2P网节点协作交互和资源路由上。这类系统中，目前存在很多使用传统的布鲁姆过滤器来表达庞大的数据集合以提高查找效率的应用。通过布鲁姆过滤器汇总(summary)节点的存储信息形成一个位串向量，系统中每个节点拥有若干个这样的汇总向量，每个向量代表着该节点某个搜索方向可能拥有的信息集合。当节点被请求响应某个检索请求时，通过查询这些向量，能够有效地指导信息的搜索方向。而在实际应用中，存储的信息资源是多属性的信息资源，传统的布鲁姆过滤器已经不适合来表示和查找此类信息，CMDBF同样可以辅助这类应用的展开。CMDBF和以往的布鲁姆过滤器相比，由于其可以支持多域(多属性)集合的表示和元素的查找，因此比现有的布鲁姆过滤器具有更加广泛的应用前景。6 结束语布鲁姆过滤器对大规模数据集合表示与查找很有效。本文研究如何将布鲁姆过滤器由一维扩展到多维的方法，仔细分析现有的MDBF算法的运行机理，针对其对元素表达时缺乏元素整体表示的缺陷，提出一种两步查询的改进的联合多维布鲁姆过滤器CMDBF，将元素的表示和查询分为两步进行。MDBF的查找作为元素查找第一步，第二步是利用联合元素各属性域查询结果，做进一步的查询确认，仿真实验表明，新的CMDBF过滤器和MDBF相比，以增加少量空间为代价，误判率降低明显。参考文献：1BLOOM B. Space/time trade-offs in hash coding with allowable errorsJ. Communications of the ACM, 1970,13(7): 422-426.2BRODER A, MITZENMACHER M. Network applications of Bloom filters: a surveyJ. Internet Mathematics, 2005, 1(4): 485-509.3BONOMI F, MITZENMACHER M, PANIGRAPHY R, et al. Beyond bloom filters: from approximate membership checks to approximate state machinesA. Proc of ACM SIGCOMM 2006C. Pisa, Italy, 2006. 315-326.4STOICA I, MORRIS R, KARGER D, et al. Chord: a scalable peerto-peer lookup service for Internet applicationsA. Proc of ACM SIGCOMM 2001C. San Francisco, 2001. 149-160.5谢鲲, 张大方, 谢高刚等. 基于轨迹标签的无结构P2P副本一致性维护算法J. 软件学报, 2007, 18(1): 105-116.XIE K, ZHANG D F, XIE G G, et al. A trace label based consistency maintenance algorithm in unstructured P2P systemsJ. Journal of Software, 2007, 18(1): 105-116.6RHEA S C, KUBIATOWICZ J. Probabilistic location and routingA. Proc of INFOCOM2002C. New York, 2002. 1248-1257.7WHITAKER A, WETHERALL D. Forwarding without loops in IcarusA. Proc of Open Architectures and Network ProgrammingC. New York, 2002. 63-75.8SARANG D, PRAVEEN K, DAVID E T. Longest prefix matching using bloom filtersA. Proc of ACM Sigcomm 2003C. Karlsruhe, Germany, 2003. 201-212.9龚俭, 彭艳兵, 杨望等. 基于BloomFilter的大规模异常TCP连接参数再现方法J. 软件学报, 2006, 17(3): 434-444.GONG J, PENG Y B, YANG W, et al. Reconstructing the parameter for massive abnormal TCP connections with Bloom filterJ. Journal of Software,2006, 17(3): 434-444.10DINESH S, ZHI G, BETUL B, et al. Automatic compilation framework for Bloom filter based intrusion detectionA. Proc of ARC2006C. 2006. 413-418.11FAN Y, HAIYUN L, SONGWU L, et al. Statistical en-route filtering of injected false data in sensor networksJ. IEEE Journal on Selected Areas in Communications, 2005, 23(4): 839-850.12FAN D, DAVOOD R. Approximately detecting duplicates for streaming data using stable bloom filtersA. Proc of SIGMOD 2006C. Illinois, USA, 2006. 27-29.13FAN L, CAO P, Almeida J, et al. Summary cache: a scalable wide-area Web cache sharing protocolJ. IEEE/ACM Trans on Networking, 2000, 8(3): 281-293.14MITZENMACHER M. Compressed bloom filtersJ. IEEE/ACM Trans on Networking, 2002, 10(5): 604-612.15SAAR C, YOSSI M. Spectral bloom filtersA. Proc ACM SIGMOD International Conference on Management of DataC. San Diego. California, 2003. 241-252.16肖明忠, 代亚非, 李晓明. 拆分型Bloom FilterJ. 电子学报. 2004, 3 2(2): 241-245.XIAO M Z, DAI Y F, LI X M. Split Bloom Filt