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

摘要

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