科学研究

数据重删系统中的非对称极值分块算法

来源:武汉光电国家研究中心   作者:  发布时间:2015年05月26日  点击量:

  今天我们已步入大数据时代,海量的数据给存储和传输带来了巨大的挑战。近期的研究表明,存储系统和网络流量中都存在大量的重复数据,因此重复数据删除技术受到企业和学术界越来越多的关注。重复数据删除包括数据分块、指纹计算、索引、存储(或传输)四个环节,其中数据分块负责将输入数据流分成多个数据块。但是目前的分块算法过于耗时,导致数据分块环节成为重复数据删除流程中的性能瓶颈。
  武汉光电国家实验室信息存储与光显示功能实验室的张宇成博士等人在冯丹教授的指导下,提出一种基于非对称极值的分块算法(Asymmetric Extremum Chunking Algorithm,简称AE算法),打破了数据去重系统中的数据分块环节的性能瓶颈。AE算法查找非对称区域内的局部极值,并利用局部极值不容易被替换掉这一原理避免边界偏移问题。与现有分块算法相比,AE算法的计算开销更小,块长方差更小,同时可检测到更多的低熵字符串。实验结果表明,AE可获得与现有分块算法相当或更高的去重率,同时达到现有算法3倍多的分块吞吐量。
  2015年4月26日,这项研究成果“ 数据重删系统中的基于内容的非对称极值分块算法”(AE:An Asymmetric Extremum Content Defined Chunking Algorithm for Fast and Bandwidth-Efficient Data Deduplication)发表在中国计算机学会A类国际会议INFOCOM 2015上,INFOCOM是IEEE组织在通信网络领域的旗舰型会议,同时也是中国计算机学会规定的A类会议。本届会议收到1640篇投稿,录用316篇论文,录用率为19%。

  相关研究工作得到国家973计划(2011CB302301)、国家自然科学基金(61025008,61173043,61232004,6140050892)和国家863计划(2013AA013203)等项目的支持。

            实验结果:分块吞吐量

(责任编辑:陈智敏)