分档布鲁姆过滤器的查询算法

摘要：

布鲁姆过滤器是一种能够简洁地表示集合并支持集合查询的数据结构,广泛应用于数据库、网络和分布式系统中.针对现有的布鲁姆过滤器没有考虑查询失效代价这一缺陷,文中提出一种新的代价敏感的分档布鲁姆过滤器查询算法.它将元素根据不同的查询代价分为不同的子集,通过考查每档子集最低查询失效率的关系,建立由每档子集合最低查询失效假阳性概率表示的集合最低查询失效总代价目标函数,使用类目标函数梯度遗传算法获得每档的最优Hash函数个数ki,完成集合到向量的映射与查找.仿真实验结果表明,使用新结构的查询算法和标准布鲁姆过滤器算法相比,所用的查询计算时间基本相同,因为区分对待集合元素,查询失效总代价仅为标准算法的27%.

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

所属期刊栏目：30

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金60473031;60273070;60403031;90604015;国家高技术研究发展计划863计划2005AA121560;湖南省科技计划2006GK3101

在线出版日期：2007-05-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：597-607