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

摘要：

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

关键词：分布式系统、覆盖查询、布鲁姆过滤器、范围规则、前缀编码

所属期刊栏目：42

分类号：TP311.12(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61472131,61272546,61572184

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

页数：共6页

页码：301-306