一种面向覆盖查询的布鲁姆过滤器设计

• 作者: 伍菊红 谢鲲
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 分布式系统 覆盖查询 布鲁姆过滤器 范围规则 前缀编码
• 年，卷（期）: 2016,（4）
• 所属期刊栏目: 开发研究与工程应用
• 页码范围: 301-306
• 页数: 6页
• 分类号: TP311.12
• 字数: 5609字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2016.04.051

摘要

在分布式系统中,覆盖查询对于保持文件的完整性以及数据的一致性有重要作用.虽然布鲁姆过滤器可以支持快速的元素从属查询,但是布鲁姆过滤器只能存储和表示离散的数据集合.为此,用前缀集合表示范围规则,并提出一个前缀编码的转化函数,将每一个前缀码转化为唯一对应的二进制串.为了支持覆盖查询,将计数布鲁姆过滤器与一组链表相结合,设计一个BFrange系统来存储包含规则标识以及具体存储元素的二元组.通过BFrange进行覆盖查询,使查询时间与存储的规则个数无关,复杂度仅为O(1).仿真实验结果验证了BFrange能实现高效和准确的覆盖查询.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	谢鲲	湖南大学信息科学与工程学院	54	529	12.0	21.0
2	伍菊红	湖南大学信息科学与工程学院	1	2	1.0	1.0