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

Combine multi-dimension Bloom filter for membership queries

作　　者：谢鲲[1,4] 秦拯[2] 文吉刚[1] 张大方[2] 谢高岗[3] 

机构地区：[1]湖南大学计算机与通信学院,湖南长沙410082 [2]湖南大学软件学院,湖南长沙410082 [3]中国科学院计算技术研究所网络与普适计算研究部,北京100080 [4]香港理工大学电子计算学系,中国香港

出　　处：《通信学报》2008年第1期56-64,共9页Journal on Communications

基　　金：国家自然科学基金资助项目(60673155,90604015,60703097);湖南省科技计划基金资助项目(2006FJ4110);广东省科技计划基金资助项目(2007B01020043)~~

摘　　要：分析了现有多维布鲁姆过滤器查询算法(MDBF)工作原理,提出了一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF)查询算法。CMDBF新增一个用于表示元素整体的联合布鲁姆过滤器CBF,CMDBF中元素表示和查找分两步进行。将MDBF的各属性的表示和查询作为第一步,第二步联合元素所有属性域,利用CBF完成元素整体的表示和查询确认。理论分析和仿真实验结果表明,CMDBF能够支持多维集合元素的简洁表示和查询,相比MDBF查询误判率降低明显。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.

关 键 词：计算机网络 分布式计算 分布式消息系统 集合元素查询 多维布鲁姆过滤器 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]