基于双布鲁姆过滤器的数据排重技术

计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (23): 198-202.

基于双布鲁姆过滤器的数据排重技术

席晔文，杨金民

湖南大学信息科学与工程学院，长沙 410082

出版日期:2014-12-01 发布日期:2014-12-12

Duplicate data delete technology based on double bloom filter

XI Yewen, YANG Jinmin

School of Information Science and Technology, Hunan University, Changsha 410082, China

Online:2014-12-01 Published:2014-12-12

摘要/Abstract

摘要： 针对文件级单布鲁姆过滤器排重算法只能以文件为单位进行数据排重，数据块级单布鲁姆过滤器排重算法耗时过多的缺点，采用2个布鲁姆过滤器，创建文件级和数据块级2级数据排重的算法结构。实验结果表明，双布鲁姆过滤器排重算法可以以数据块为单位对数据排重，在保持低假阳性误判率的同时，相比数据块级单布鲁姆过滤器排重算法耗时缩短了43%~68%。

关键词: 重复数据删除, 集合元素查询, 布鲁姆过滤器, MD5, 假阳性误判率

Abstract: Aiming at the disadvantage of file level single bloom filter duplicate data delete algorithm deletes duplicate data only at file size, block level single bloom filter duplicate data delete algorithm’s time-consuming is too much. In this paper, it uses 2 bloom filter, creates a 2 level duplicate data delete algorithm structure-file level and block level. The experimental results show that, double bloom filter duplicate data delete algorithm could delete duplicate data at block level, keep false positive error rate at a low level, time-consuming gets 43%~68% shorter compared with block level single bloom filter duplicate data delete algorithm.

Key words: duplicate data delete, query elements, bloom filter, MD5, false positive error rate

席晔文，杨金民. 基于双布鲁姆过滤器的数据排重技术[J]. 计算机工程与应用, 2014, 50(23): 198-202.

XI Yewen, YANG Jinmin. Duplicate data delete technology based on double bloom filter[J]. Computer Engineering and Applications, 2014, 50(23): 198-202.

[1]	赵晓永1，陈晨2. 面向云平台的二代测序数据近似去重方法研究[J]. 计算机工程与应用, 2017, 53(23): 1-5.
[2]	李洪奇，冯海波，张伟，杨中国，宋伟城. 基于字集特征向量的网页消重改进算法[J]. 计算机工程与应用, 2017, 53(2): 53-57.
[3]	徐阳. 一个网络文件存储系统TNS关键技术[J]. 计算机工程与应用, 2015, 51(2): 71-75.
[4]	孟金凤，高仲合. 基于DCBF的流抽样测量算法[J]. 计算机工程与应用, 2015, 51(17): 92-95.
[5]	王春龙，刘渊，郑哲渊. 基于LRU和扩展CBF的网络大流检测[J]. 计算机工程与应用, 2015, 51(13): 66-71.
[6]	刘健1，王玲1，吴桐1，2. 基于级联混沌系统改进的图像加密算法[J]. 计算机工程与应用, 2015, 51(12): 68-73.
[7]	郭亮，杨金民. 融入MD5的HASH线性获取增量算法研究[J]. 计算机工程与应用, 2014, 50(23): 136-139.
[8]	田小梅1，2，张大方1，史长琼1，杨晓波1. 双布鲁姆过滤器法查询集合成员[J]. 计算机工程与应用, 2012, 48(28): 10-15.
[9]	王欢，李战怀，张晓. 支持连续数据保护的云备份系统架构设计[J]. 计算机工程与应用, 2012, 48(1): 90-93.
[10]	陈少晖^1，2，翟晓宁^1，2，阎娜^1，2，苏国兴^1，2. MD5 算法破译过程解析[J]. 计算机工程与应用, 2010, 46(19): 109-112.
[11]	林晶,黄青松,张晶. 基于改进MD5算法的数据篡改检测方法[J]. 计算机工程与应用, 2008, 44(33): 148-150.