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

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