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

A Design of Bloom Filter for Cover Query

作　　者：谢鲲[1] 伍菊红 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082

出　　处：《计算机工程》2016年第4期301-306,共6页Computer Engineering

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

摘　　要：在分布式系统中,覆盖查询对于保持文件的完整性以及数据的一致性有重要作用。虽然布鲁姆过滤器可以支持快速的元素从属查询,但是布鲁姆过滤器只能存储和表示离散的数据集合。为此,用前缀集合表示范围规则,并提出一个前缀编码的转化函数,将每一个前缀码转化为唯一对应的二进制串。为了支持覆盖查询,将计数布鲁姆过滤器与一组链表相结合,设计一个BFrange系统来存储包含规则标识以及具体存储元素的二元组。通过BFrange进行覆盖查询,使查询时间与存储的规则个数无关,复杂度仅为O(1)。仿真实验结果验证了BFrange能实现高效和准确的覆盖查询。Cover query plays an important role in maintaining the integrity of files and the consistency of data in distributed systems. Although Bloom filter can support quick membership query,it can only represent a discrete data set. This paper utilizes a set of prefix to represent the range rule and proposes a prefix-code transformation function to transform each prefix into an unique binary code. To facilitate cover query, this paper further designs a BFrange system to store the two tuple containing rules and specific storage elements by combining the counting Bloom filter with a set of list. The query time complexity under BFrange is only O （ 1 ）, which does not depend on the number of the rules. Simulation results demonstrate that the BFrange system can support efficient and accurate cover query.

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

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]