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

Deduplication algorithm based on condensed nearest neighbor rule for deduplication metadata

作　　者：姚文斌[1,2] 叶鹏迪[3] 李小勇[4] 常静坤[1,2] 

机构地区：[1]北京邮电大学智能通信软件与多媒体北京市重点实验室,北京100876 [2]北京邮电大学计算机学院,北京100876 [3]中国铁道科学研究院机车车辆研究所,北京100081 [4]北京邮电大学可信分布式计算与服务教育部重点实验室,北京100876

出　　处：《通信学报》2015年第8期1-7,共7页Journal on Communications

基　　金：国家自然科学基金资助项目(61370069);国家高技术研究发展计划("863"计划)基金资助项目(2012AA012600);中央高校基本科研业务费专项基金资助项目(BUPT2011RCZJ16)~~

摘　　要：随着重复数据删除次数的增加,系统中用于存储指纹索引的清单文件等元数据信息会不断累积,导致不可忽视的存储资源开销。因此,如何在不影响重复数据删除率的基础上,对重复数据删除过程中产生的元数据信息进行压缩,从而减小查重索引,是进一步提高重复数据删除效率和存储资源利用率的重要因素。针对查重元数据中存在大量冗余数据,提出了一种基于压缩近邻的查重元数据去冗算法Dedup2。该算法先利用聚类算法将查重元数据分为若干类,然后利用压缩近邻算法消除查重元数据中相似度较高的数据以获得查重子集,并在该查重子集上利用文件相似性对数据对象进行重复数据删除操作。实验结果表明,Dedup2可以在保持近似的重复数据删除比的基础上,将查重索引大小压缩50%以上。Building effective deduplication index in the memory could reduce disk access times and enhance chunk fin- gerprint lookup speed, which was a big challenge for deduplication algorithms in massive data environments. As dedu- plication data set had many samples with high similarity, a deduplication algorithm based on condensed nearest neighbor rule, which was called Dedup2, was proposed. Dedup2 uses clustering algorithrn 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 deduplieation metadata. After that it can get the subset of deduplication metadata. Based on this subset, new data ob- jects will be deduplicated based on the principle of data similarity. The results of experiments show that Dedup2 can reduce the size of deduplication data set more than 50% effectively while maintain similar deduplication ratio.

关 键 词：重复数据删除 查重元数据 近邻压缩规则 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]