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

An Improved Dynamic Count Filter Realization Method

作　　者：岳未然 赵辉[1] 徐龙[1] 

机构地区：[1]四川大学计算机学院,成都610064

出　　处：《网络新媒体技术》2017年第5期42-47,共6页Network New Media Technology

基　　金：国家重点研发计划(2016yfb0800604;2016yfb0800605);国家自然科学基金项目(61572334)

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

关 键 词：计数器 布隆过滤器 计数布隆过滤器 动态计数过滤器 动态计数布隆过滤器 布隆过滤器向量 溢出过滤器向量 多维动态计数过滤器 

分 类 号：TP332[自动化与计算机技术—计算机系统结构]