一种改进的Dynamic Count Filter实现方法

摘要

布隆过滤器常用来快速判断给定元素是否在一个集合中,动态计数过滤器是布隆过滤器的一种改进.本文针对当前动态计数过滤器处理数据溢出时,新建以及重建溢出过滤器向量时间开销大的问题,提出了一种基于布隆过滤器向量的改进实现方法.该方法采用多个布隆过滤器向量替代溢出过滤器向量,以避免溢出过滤器的建立,同时也避免了其重建时进行的数据拷贝.实验结果表明,该方法较动态计数过滤器和动态计数布隆过滤器缩减了处理数据溢出所需的时间,大大提升过滤器操作效率,并且较动态计数布隆过滤器节省了内存空间.%Bloom filters are often used to charge if a given element is in a set quickly,and the dynamic count filter is an improvement over a Bloom filter.In this paper,an improved method based on Bloom Filter Vector is proposed to deal with the problem that the time cost of new and reconstructed Overflow Filter Vector is large when the data overflow is processed by Dynamic Count Filter.The method replaces the Overflow Filter Vector with multiple Bloom Filter Vectors to avoid the Overflow Filter and avoid the duplication of the old data.The experimental results show that this method is better than dynamic count filter and dynamic count bloom filter on reducing the processing time required for data overflow,enhancing the filter operation efficiency greatly,and also save more memory space than the dynamic count bloom filter.