| 分档布鲁姆过滤器的查询算法 |
| |
| 引用本文： | 谢鲲,闵应骅,张大方,谢高岗,文吉刚.分档布鲁姆过滤器的查询算法[J].计算机学报,2007,30(4):597-607. |
| |
| 作者姓名： | 谢鲲 闵应骅 张大方 谢高岗 文吉刚 |
| |
| 作者单位： | [1]湖南大学计算机与通信学院,长沙410082 [2]中国科学院计算技术研究所网络与普适计算研究部,北京100080 [3]湖南大学软件学院,长沙410082 |
| |
| 基金项目： | 国家自然科学基金
,
国家高技术研究发展计划(863计划)
,
湖南省科技计划 |
| |
| 摘 要： | 布鲁姆过滤器是一种能够简洁地表示集合并支持集合查询的数据结构,广泛应用于数据库、网络和分布式系统中.针对现有的布鲁姆过滤器没有考虑查询失效代价这一缺陷,文中提出一种新的代价敏感的分档布鲁姆过滤器查询算法.它将元素根据不同的查询代价分为不同的子集,通过考查每档子集最低查询失效率的关系,建立由每档子集合最低查询失效假阳性概率表示的集合最低查询失效总代价目标函数,使用类目标函数梯度遗传算法获得每档的最优Hash函数个数ki,完成集合到向量的映射与查找.仿真实验结果表明,使用新结构的查询算法和标准布鲁姆过滤器算法相比,所用的查询计算时间基本相同,因为区分对待集合元素,查询失效总代价仅为标准算法的27%.
|
| 关 键 词： | 分档布鲁姆过滤器 计算机网络 分布式计算 分布式消息系统 集合元素查询 分档 布鲁姆 过滤器 查询算法 Membership Filters 标准算法 集合元素 区分对待 时间 查询计算 结构 结果 仿真实验 查找 映射 向量 数个数 Hash 最优 |
| 修稿时间： | 2005-09-292006-12-14 |
Basket Bloom Filters for Membership Queries |
| |
| XIE Kun,MIN Ying-Hua,ZHANG Da-Fang,XIE Gao-Gang,WEN Ji-Gang.Basket Bloom Filters for Membership Queries[J].Chinese Journal of Computers,2007,30(4):597-607. |
| |
| Authors: | XIE Kun MIN Ying-Hua ZHANG Da-Fang XIE Gao-Gang WEN Ji-Gang |
| |
| Affiliation: | 1.College of Computer and Communication, Hunan University, Changsha 410082;2.Networking and Ubiquitous Computing Department, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080;3.School of Software, Hunan University, Changsha 410082 |
| |
| Abstract: | |
| |
| Keywords: | Basket Bloom Filter computer networks distributed computing distributed information system membership query |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
