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

被引:14
作者
谢鲲 [1 ]
闵应骅 [2 ]
张大方 [3 ]
谢高岗 [2 ]
文吉刚 [1 ]
机构
[1] 湖南大学计算机与通信学院
[2] 中国科学院计算技术研究所网络与普适计算研究部
[3] 湖南大学软件学院
关键词
分档布鲁姆过滤器; 计算机网络; 分布式计算; 分布式消息系统; 集合元素查询;
D O I
暂无
中图分类号
TP311.11 [];
学科分类号
081202 ; 0835 ;
摘要
布鲁姆过滤器是一种能够简洁地表示集合并支持集合查询的数据结构,广泛应用于数据库、网络和分布式系统中.针对现有的布鲁姆过滤器没有考虑查询失效代价这一缺陷,文中提出一种新的代价敏感的分档布鲁姆过滤器查询算法.它将元素根据不同的查询代价分为不同的子集,通过考查每档子集最低查询失效率的关系,建立由每档子集合最低查询失效假阳性概率表示的集合最低查询失效总代价目标函数,使用类目标函数梯度遗传算法获得每档的最优Hash函数个数ki,完成集合到向量的映射与查找.仿真实验结果表明,使用新结构的查询算法和标准布鲁姆过滤器算法相比,所用的查询计算时间基本相同,因为区分对待集合元素,查询失效总代价仅为标准算法的27%.
引用
收藏
页码:597 / 607
页数:11
相关论文
共 2 条
[1]   集中管理式Web缓存系统及性能分析 [J].
姜彩萍 ;
李子木 ;
杨凤杰 .
小型微型计算机系统, 2004, (08) :1428-1431
[2]   利用目标函数梯度的遗传算法 [J].
何新贵 ;
梁久祯 .
软件学报, 2001, (07) :981-986