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

摘要

布隆过滤器常用来快速判断给定元素是否在一个集合中,动态计数过滤器是布隆过滤器的一种改进。本文针对当前动态计数过滤器处理数据溢出时,新建以及重建溢出过滤器向量时间开销大的问题,提出了一种基于布隆过滤器向量的改进实现方法。该方法采用多个布隆过滤器向量替代溢出过滤器向量,以避免溢出过滤器的建立,同时也避免了其重建时进行的数据拷贝。实验结果表明,该方法较动态计数过滤器和动态计数布隆过滤器缩减了处理数据溢出所需的时间,大大提升过滤器操作效率,并且较动态计数布隆过滤器节省了内存空间。