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

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 2007年中文

	分档布鲁姆过滤器的查询算法
	谢高岗; 闵应骅; 谢鲲; 张大方; 文吉刚
刊名	计算机学报
	2007
期号	第4期页码:597—607
关键词	分档布鲁姆过滤器计算机网络分布式计算分布式消息系统集合元素查询
英文摘要	布鲁姆过滤器是一种能够简洁地表示集合并支持集合查询的数据结构，广泛应用于数据库、网络和分布式系统中.针对现有的布鲁姆过滤器没有考虑查询失效代价这一缺陷，文中提出一种新的代价敏感的分档布鲁姆过滤器查询算法.它将元素根据不同的查询代价分为不同的子集，通过考查每档子集最低查询失效率的关系，建立由每档子集合最低查询失效假阳性概率表示的集合最低查询失效总代价目标函数，使用类目标函数梯度遗传算法获得每档的最优Hash函数个数ki，完成集合到向量的映射与查找.仿真实验结果表明，使用新结构的查询算法和标准布鲁姆过滤器算法相比，所用的查询计算时间基本相同，因为区分对待集合元素，查询失效总代价仅为标准算法的27%.
语种	中文
公开日期	2010-10-20
内容类型	期刊论文
源URL	[http://ictir.ict.ac.cn/handle/311040/753]
专题	中国科学院计算技术研究所期刊论文_2007年中文
推荐引用方式 GB/T 7714	谢高岗,闵应骅,谢鲲,等. 分档布鲁姆过滤器的查询算法[J]. 计算机学报,2007(第4期):597—607.
APA	谢高岗,闵应骅,谢鲲,张大方,&文吉刚.(2007).分档布鲁姆过滤器的查询算法.计算机学报(第4期),597—607.
MLA	谢高岗,et al."分档布鲁姆过滤器的查询算法".计算机学报 .第4期(2007):597—607.