一种可扩展的布鲁姆过滤器查询方法及其元素插入方法

摘要

本发明提供一种可扩展布鲁姆过滤器(Scalable Bloom filter)查询方法，在数据集元素个数增长的情况下，通过添加长度成倍增长过滤器向量来保持很低的误判率，并给出了一种可扩展布鲁姆过滤器查询方法的元素插入方法。实验表明，可扩展布鲁姆过滤器的元素查询误判率永远小于动态布鲁姆过滤器，可以控制查询误判率在1％，在3.0GHz的CPU机器中，一次元素查询时间仅20μs，比DBF查询速度快很多倍。本发明在现有的布鲁姆过滤器应用领域都可以适应，由于支持集合的动态扩展，因此比现有的布鲁姆过滤器具有更加广泛的应用前景。

主权项

1、一种可扩展布鲁姆过滤器查询方法，其特征在于，该方法为：1)布鲁姆过滤器的扩展：当可扩展布鲁姆过滤器SBF所表示的集合元素增长超过可扩展布鲁姆过滤器容量限制时，添加一个长度为前一个可扩展布鲁姆过滤器向量的2倍的向量，即添加了可扩展布鲁姆过滤器向量的向量长度mi＝2mi-1，此时添加了可扩展布鲁姆过滤器向量的向量容量限制也为前一个向量容量限制的2倍，即ni＝2ni-1；2)可扩展布鲁姆过滤器元素查询步骤：第一步：利用SBF查询元素x是否在集合S中，令j＝i；第二步：通过k个哈希函数计算x在SBFj的k个映射位，检查所有位是否都为1；第三步：所述结果为是时，元素x是SBFj表示的元素，x在集合S中，返回True；第四步：所述结果为否时，元素x不是SBFj表示的元素，需要继续检查x是否为SBFj-1表示的元素，j←j-1，转到2持续检查x是否为当前向量SBFj直至j＝-1。