基于压缩近邻的查重元数据去冗算法设计

doi:10.11959/j.issn.1000-436x.2015226

Abstract

Abstract:

Building effective deduplication index in the memory could reduce disk access times and enhance chunk fingerprint lookup speed,which was a big challenge for deduplication algorithms in massive data environments.As deduplication data set had many samples with high similarity,a deduplication algorithm based on condensed nearest neighbor rule,which was called Dedup²,was proposed.Dedup²uses clustering algorithm to divide the original deduplication metadata into several categories.According to these categories,it employs condensed nearest neighbor rule to remove the highest similar data in the deduplication metadata.After that it can get the subset of deduplication metadata.Based on this subset,new data objects will be deduplicated based on the principle of data similarity.The results of experiments show that Dedup²can reduce the size of deduplication data set more than 50% effectively while maintain similar deduplication ratio.

Key words: deduplication, deduplication metadata, condensed nearest neighbor rule

Wen-bin YAO,Peng-di YE,Xiao-yong LI,Jing-kun CHANG. Deduplication algorithm based on condensed nearest neighbor rule for deduplication metadata[J]. Journal on Communications, 2015, 36(8): 1-7.

Figures/Tables 6

References 23

[1]	ZHU B , LI K , PATTERSON H . Avoiding the disk bottleneck in the data domain deduplication file system[A]. Proceedings of the 6th USENIX Conference on File and Storage Technologies,USENIX Association[C]. 2008. 1-14.
[2]	LILLIBRIDGE M , ESHGHI K , BHAGWAT D ,et al. Sparse indexing:large scale,inline deduplication using sampling and locality[A]. Proccedings of the 7th Conference on File and Storage Technologies,USENIX Association[C]. 2009. 111-123.
[3]	BHAGWAT D , ESHGHI K , LONG D ,et al. Extreme binning:scalable,parallel deduplication for chunk-based file backup[A]. In Modeling,Analysis ＆ Simulation of Computer and Telecommunication Systems,IEEE International Symposium[C]. IEEE, 2009. 1-9.
[4]	XIA W , JIANG H , FENG D ,et al. SiLo:a similarity-locality based near-exact deduplication scheme with low RAM overhead and high throughput[A]. Proceedings of the 2011 USENIX Annual Technical Conference(ATC),USENIX Association[C]. 2011. 26-28.
[5]	ARONOVICH L , ASHER R , BACHMAT E ,et al. The design of a similarity based deduplication system[A]. Proceedings of SYSTOR 2009,The Israeli Experimental Systems Conference[C]. ACM, 2009. 1-14.
[6]	ROMA?SKI B , HELDT ? ? , KILIAN W ,et al. Anchor-driven subchunk deduplication[A]. Proceedings of the 4th Annual International Conference on Systems and Storage[C]. 2011. 16-28.
[7]	ZHANG Z , BHAGWAT D , LITWIN W ,et al. Improved deduplication through parallel binning[A]. Performance Computing and Communications Conference(IPCCC),2012 IEEE 31st International[C]. 2012. 130-141.
[8]	DOUGLIS F , IYENGAR A . Application-specific deltaencoding via resemblance detection[A]. Proceedings of the 2003 USENIX Annual Technical Conference[C]. San Antonio,Texas, 2003. 113-126.
[9]	BRODER A Z , MITZENMACHER M . Network applications of Bloom filters:a survey[J]. Internet Mathematics, 2004,1(4): 485-509.
[10]	TAN L J , YAO W B , LIU Z Y.et al . CDFS:a cloud-based deduplication filesystem[J]. Advanced Science Letters,American Scientific Publishers, 2012,9(1): 855-860.
[11]	TEODOSIU D , BJORNER N , GUREVICH Y ,et al. Optimizing file replication over limited-bandwidth networks using remote differential compression[R]. Technical Report MSR-TR-2006-157,Microsoft Research, 2006.
[12]	YAO W B , YE P D . Simdedup:a new deduplication scheme based on simhash[A]. In Web-Age Information Management[C]. Springer Berlin Heidelberg, 2013. 79-88.
[13]	CHARIKAR M . Similarity estimation techniques from rounding algorithms[A]. Proc 34th Annual Symposium on Theory of Computing(STOC2002)[C]. 2002. 380-388.
[14]	MEISTER D , BRINKMANN A . Multi-level comparison of data deduplication in a backup scenario[A]. Proceedings of SYSTOR 2009,The Israeli Experimental Systems Conference[C].ACM, 2009.
[15]	MEYER D T , BOLOSKY W J . A study of practical deduplication[J]. ACM Transactions on Storage(TOS), 2012,7(4): 14.
[16]	WALLACE G , DOUGLIS F , QIAN H ,et al. Characteristics of backup workloads in production systems[A]. Proceedings of the Tenth USENIX Conference on File and Storage Technologies(FAST’12)[C]. 2012.
[17]	WEI J , JIANG H , ZHOU K ,et al. MAD2:a scalable high-throughput exact deduplication approach for network backup services[A]. Mass Storage Systems and Technologies(MSST),2010 IEEE 26th Symposium[C].IEEE, 2010. 1-14.
[18]	KAISER J , MEISTER D , BRINKMANN A ,et al. Design of an exact data deduplication cluster[A]. Mass Storage Systems and Technologies(MSST),2012 IEEE 28th Symposium[C].IEEE, 2012. 1-12.
[19]	BALACHANDRAN S , CONSTANTINESCU C . Sequence of hashes compression in data de-duplication[A]. Data Compression Conference,DCC 2008[C].IEEE, 2008.505.
[20]	CONSTANTINESCU C , PIEPER J , LI T . Block size optimization in deduplication systems[A]. Data Compression Conference,DCC'09[C].IEEE, 2009. 442-442.
[21]	ESHGHI K , LILLIBRIDGE M , WILCOCK L ,et al. Jumbo store:providing efficient incremental upload and versioning for a utility rendering service[A]. FAST[C]. 2007. 123-138.
[22]	MEISTER D , BRINKMANN A,Sü? T . File recipe compression in data deduplication systems[A]. Proceedings of 11th USENIX Conference on File and Storage Technologies(FAST)[C]. 2013. 175-182.
[23]	HART P E . The condensed nearest neighbor rule[J]. IEEE Transactions on Information Theory IT-14, 1968: 515-516.

Metrics

Recommended 0

No Suggested Reading articles found!

Deduplication algorithm based on condensed nearest neighbor rule for deduplication metadata

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 23

Related Articles 11

Metrics

Recommended 0

[1]	Guanxiong HA, Qiaowen JIA, Hang CHEN, Chunfu JIA. Data popularity-based encrypted deduplication scheme without third-party servers [J]. Journal on Communications, 2022, 43(8): 17-29.
[2]	Chunfu JIA, Guanxiong HA, Shaoqiang WU, Hang CHEN, Ruiqi LI. AONT-and-NTRU-based rekeying scheme for encrypted deduplication [J]. Journal on Communications, 2021, 42(10): 67-80.
[3]	Xin TANG,Linna ZHOU,Weijie SHAN,Dan LIU. Threshold re-encryption based secure deduplication method for cloud data with resistance against side channel attack [J]. Journal on Communications, 2020, 41(6): 98-111.
[4]	Chunfu JIA,Guanxiong HA,Ruiqi LI. Data access control policy of encrypted deduplication system [J]. Journal on Communications, 2020, 41(5): 72-83.
[5]	Xiangsong ZHANG,Chen LI,Zhenhua LIU. Key-exposure resilient integrity auditing scheme with encrypted data deduplication [J]. Journal on Communications, 2019, 40(4): 95-106.
[6]	Jinbo XIONG,Yuanyuan ZHANG,Youliang TIAN,Zuobin YING,Qi LI,Rong MA. Cloud data secure deduplication scheme via role-based symmetric encryption [J]. Journal on Communications, 2018, 39(5): 59-73.
[7]	Xiao-yong GUO,An-min FU,Bo-yu KUANG,Wei-jia DING. Secure deduplication and integrity audit system based on convergent encryption for cloud storage [J]. Journal on Communications, 2017, 38(Z2): 156-163.
[8]	Jin-bo XIONG,Su-ping LI,Yuan-yuan ZHANG,Xuan LI,EA-yong Y,Zhi-qiang YAO. PoSW:novel secure deduplication scheme for collaborative cloud applications [J]. Journal on Communications, 2017, 38(7): 18-27.
[9]	Chao YANG,Qian JI,Si-chun XIONG,Mao-zhen LIU,Jian-feng MA,Qi JIANG,Lin BAI. New method for file deduplication in cloud storage [J]. Journal on Communications, 2017, 38(3): 25-33.
[10]	Jin-bo XIONG,Yuan-yuan ZHANG,Feng-hua LI,Su-ping LI,Jun REN,Zhi-qiang YAO. Research progress on secure data deduplication in cloud [J]. Journal on Communications, 2016, 37(11): 169-180.
[11]	Yue CHEN,Chao-ling LI,Ju-long LAN,Kai-chun JIN,Zhong-hui WANG. Secure sensitive data deduplication schemes based on deterministic/probabilistic proof of file ownership [J]. Journal on Communications, 2015, 36(9): 1-12.