Winnowing指纹串匹配的重复数据删除算法

doi:10.11772/j.issn.1001-9081.2017082023

计算机应用 ›› 2018, Vol. 38 ›› Issue (3): 677-681.DOI: 10.11772/j.issn.1001-9081.2017082023

Winnowing指纹串匹配的重复数据删除算法

王青松, 葛慧

辽宁大学信息学院, 沈阳 110036

收稿日期:2017-08-18 修回日期:2017-09-28 出版日期:2018-03-10 发布日期:2018-03-07
通讯作者: 王青松
作者简介:王青松(1974-),男,辽宁岫岩人,副教授,硕士,主要研究方向:大数据、数据挖掘;葛慧(1991-),女,河南平顶山人,硕士研究生,主要研究方向:重复数据删除。
基金资助:
国家自然科学基金资助项目（61502215）。

Deduplication algorithm based on Winnowing fingerprint matching

WANG Qingsong, GE Hui

College of Information, Liaoning University, Shenyang Liaoning 110036, China

Received:2017-08-18 Revised:2017-09-28 Online:2018-03-10 Published:2018-03-07
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502215).

摘要/Abstract

摘要： 针对可变长度分块（CDC）的重复数据删除算法的分块大小难以控制、指纹计算对比开销大、需要预先设置参数问题，提出Winnowing指纹串匹配的重复数据删除算法（DWFM）。首先，在数据分块前引入分块大小预测模型，较准确地根据应用场景计算出合适的分块大小；然后，在计算指纹时采用ASCⅡ/Unicode编码方式作为数据块指纹；最后，在确定分块边界时，提出指纹串匹配的分块算法，不需要预先设置参数，使得指纹计算和对比开销减少。在多种数据集上的实验结果表明，相比固定长度分块（FSP）和CDC算法，DWFM在数据的重删率上提升10%左右，在指纹计算和对比开销方面减少了18%左右。因此，DWFM的分块大小和边界更加符合数据特性，减少了参数设置对重复数据删除算法性能的影响，在处理不同类型的数据时，可以有效地消除更多的重复数据。

关键词: 重复数据删除, 数据分块, 指纹串匹配, Winnowing, 分块预测

Abstract: There are some problems in big data that the chunking size of the deduplication algorithm for Content-Defined Chunking (CDC) is difficult to control, the expense of fingerprint calculation and comparison is high, and the parameter needs to be set in advance. Thus, a Deduplication algorithm based on Winnowing Fingerprint Matching (DWFM) was proposed. Firstly, the chunking size prediction model was introduced before chunking, which can accurately calculate proper chunking size according to the application scenario. Then, the ASCⅡ/Unicode was used as the data block fingerprint in the calculation of the fingerprint. Finally, when determining the block boundary, the proposed algorithm based on chunk fingerprint matching does not need to set the parameters in advance to reduce fingerprint calculation and contrast overhead. The experimental results on a variety of datasets show that DWFM is about 10% higher than FSP (Fixed-Sized Partitioning) and CDC algorithms in deduplication rate, and about 18% in fingerprint computing and contrast overhead. As a result, the chunking size and boundaries of DWFM are more consistent with data characteristics, reducing the impact of parameter settings on the performance of deduplication algorithms, meanwhile, effectively eliminating more duplicate data when dealing with different types of data.

Key words: data deduplication, data chunking, fingerprint matching, Winnowing, chunking prediction

中图分类号:

TP311

王青松, 葛慧. Winnowing指纹串匹配的重复数据删除算法[J]. 计算机应用, 2018, 38(3): 677-681.

WANG Qingsong, GE Hui. Deduplication algorithm based on Winnowing fingerprint matching[J]. Journal of Computer Applications, 2018, 38(3): 677-681.

参考文献

[1] SUN Y, ZENG C Y, CHUNG J, et al. Online data deduplication for in-memory big-data analytic systems[C]//Proceedings of 2017 IEEE International Conference on Communications. Piscataway, NJ:IEEE, 2017:1-7.
[2] ZHENG Y, DING W X, YU X X, et al. Deduplication on encrypted big data in cloud[J]. IEEE Transactions on Big Data, 2016, 2(2):138-150.
[3] 熊金波,张媛媛,李凤华,等.云环境中数据安全去重研究进展[J].通信学报,2016,37(11):169-180.(XIONG J B, ZHANG Y Y, LI F H, et al. Research progress on secure data deduplication in cloud[J]. Journal on Communications, 2016, 37(11):169-180.)
[4] BHAGWAT D, ESHGHI K, LONG D D E, et al. Extreme binning:scalable, parallel deduplication for chunk-based file backup[C]//Proceedings of 2009 IEEE International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems. Piscataway, NJ:IEEE, 2009:1-9.
[5] LI Z B, HE K J, LIN F N, et al. Deduplication of files in cloud storage based on differential bloom filter[C]//Proceedings of 20167th IEEE International Conference on Software Engineering and Service Science. Piscataway, NJ:IEEE, 2016:111-114.
[6] 张沪寅,周景才,陈毅波,等.用户感知的重复数据删除算法[J].软件学报,2015,26(10):2581-2595.(ZHANG H Y, ZHOU J C, CHEN Y B, et al. User-aware de-duplication algorithm[J]. Journal of Software, 2015, 26(10):2581-2595.)
[7] WIDODO R N S, LIM H, ATIQUZZAMAN M. A new content-defined chunking algorithm for data deduplication in cloud storage[J]. Future Generation Computer Systems, 2017, 71:145-156.
[8] WANG G P, CHEN S Y, LIN M W, et al. SBBS:a sliding blocking algorithm with backtracking sub-blocks for duplicate data detection[J]. Expert Systems with Applications, 2014, 41(5):2415-2423.
[9] 邓雪峰,孙瑞志,张永瀚,等.基于数据位图的滑动分块算法[J].计算机研究与发展,2014,51(Suppl.):30-38.(DENG X F, SUN R Z, ZHANG Y H, et al. Sliding blocking algorithm based on data bitmap[J]. Journal of Computer Research and Development, 2014, 51(Suppl.):30-38.)
[10] ZHANG Y C, HONG J, DAN F, et al. AE:an asymmetric extremum content defined chunking algorithm for fast and bandwidth-efficient data deduplication[C]//Proceedings of 2015 IEEE Conference on Computer Communications. Washington, DC:IEEE Computer Society, 2015:1337-1345.
[11] SU H N, ZHENG D, ZHANG Y H. An efficient and secure deduplication scheme based on Rabin fingerprinting in cloud storage[C]//Proceedings of 2017 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC). Piscataway, NJ:IEEE, 2017:833-836.
[12] 阎芳,李元章,张全新,等.基于对象的OpenXML复合文件去重方法研究[J].计算机研究与发展,2015,52(7):1546-1557.(YAN F, LI Y Z, ZHANG Q X, et al. Object-based data de-duplication method for OpenXML compound files[J]. Journal of Computer Research and Development, 2015, 52(7):1546-1557.)
[13] MIN J, YOON D, WON Y. Efficient deduplication techniques for modern backup operation[J]. IEEE Transactions on Computers, 2011, 60(6):824-840.
[14] 王龙翔,董小社,张兴军,等.内容分块算法中预期分块长度对重复数据删除率的影响[J].西安交通大学学报, 2016,50(12):73-78.(WANG L X, DONG X S, ZHANG X J, et al. Influence of expected chunk size on deduplication ratio in content defined chunking algorithm[J]. Journal of Xi'an Jiaotong University, 2016, 50(12):73-78.)
[15] HIRSCH M, KLEIN S T, SHAPIRA D, et al. Controlling the chunk-size in deduplication systems[C]//Proceedings of the 2015 Prague Stringology Conference. Prague:PSC, 2015:78-89.
[16] SCHLEIMER S, WILKERSON D S, AIKEN A. Winnowing:local algorithms for document fingerprinting[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2003:76-85.
[17] LULU L, BELKHOUCHE B, HAROUS S. Overview of fingerprinting methods for local text reuse detection[C]//Proceedings of the 2016 International Conference on Computing and Network Communications. Piscataway, NJ:IEEE, 2016:1-6.
[18] MEYER D T, BOLOSKY W J. A study of practical deduplication[J]. ACM Transactions on Storage, 2012,7(4):1-20.
[19] 朱永强,秦志光,江雪.基于Sunday算法的改良单模式匹配算法[J].计算机应用,2014,34(1):208-212.(ZHU Y Q, QIN Z G, JIANG X. Improved single pattern matching algorithm based on Sunday algorithm[J]. Journal of Computer Applications, 2014, 34(1):208-212.)
[20] CHO E M, KOSHIBA T. Big data cloud deduplication based on verifiable hash convergent group signcryption[C]//Proceedings of 2017 IEEE 3rd International Conference on Big Data Computing Service and Applications. Piscataway, NJ:IEEE, 2017:265-270.

Winnowing指纹串匹配的重复数据删除算法

Deduplication algorithm based on Winnowing fingerprint matching

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	韩李涛, 刘海龙, 孔巧丽, 阳凡林. 基于多核计算环境的地貌晕渲并行算法[J]. 计算机应用, 2017, 37(7): 1911-1915.
[2]	刘青, 付印金, 倪桂强, 梅建民. 基于Hadoop平台的分布式重删存储系统[J]. 计算机应用, 2016, 36(2): 330-335.