基于HDFS分布式云存储系统的重复数据检测与删除研究

传统最远点采样(FPS)算法、数据类型分析(WFC)算法的去重冗余度高,在同一数据集分块、去重检测中的数据重复率达到70~90%。基于这一实际情况,提出基于Hadoop分布式软件框架、分布式文件系统(HDFS)等云服务技术,建构用于复杂数据结构分析、数据分块去重的HDFS-SDBS云存储管理系统,使用基于文件相似度的抽样删除索引(SDBS)算法进行文件数据分块、哈希值(Hash)计算、随机抽样的相似度判定,利用元数据索引查重方式完成输入文件数据、内存数据的比对,删除相似度过高的重复数据,以提升云环境下的数据存储效率与准确率。

基于极值点分块的重复数据检测算法

重复数据检测技术能够大幅降低数据中心的存储量,节省网络带宽,减少建设和运维成本。为了克服基于内容分块(CDC)方法容易出现超长块的缺点,文章提出了基于极值点分块(EDC)的重复数据检测算法。EDC算法先计算出所有右边界在数据块上下限范围内的滑动窗口中数据的指纹,找出最后一个指纹极值,所对应的滑动窗口结束位置作为数据块的分界点,再计算该数据块的哈希值并判断是否重复块。实验结果表明,EDC算法的重复数据检测率、磁盘利用率分别是CDC算法的1.48倍和1.12倍,改进效果显著。

一种基于滑动分块的重复数据检测算法

当被插入或删除的字节接近于匹配失败数据段两侧时,会导致SBBS算法回溯功能局部甚至完全失效。为此,提出一种改进的重复数据检测算法。采用滑动与滚动相结合的窗口移动模式减少窗口计算量,利用Rsync滚动校验和算法与MD5算法优化窗口计算模式,加快匹配速度。通过回溯匹配失败数据段,检测其中的重复数据段,以提升重复数据的检测精度。实验结果表明,与SBBS算法相比,该算法在重复数据段均匀分布与非均匀分布时的查全率分别提高约4.32%和5.28%。

MapReduce模型下增量重复数据检测方法

针对重复数据检测过程中增量数据重复值检测问题进行分析,在基本近邻排序算法基础上,提出增量近邻排序比较算法。该算法通过跳动窗口形式比较相邻数据,大大减少了数据比较次数;同时引入MapReduce模型对该算法加以改进以提高其海量数据处理的能力。实验表明,改进后的增量近邻排序比较算法在保证检则结果准确的前提下,能够有效提高增量数据重复检测的速度,并且算法具有较高的稳定性,更适应海量数据环境中重复数据检测任务。

重复数据检测在多版本数据备份中的应用

分析了当前主要的重复数据检测技术,针对多版本数据的备份/还原过程提出了重复数据检测三级模型,有效地解决了检测粒度和检测开销之间的矛盾,从而减少了多版本数据备份/还原过程中的数据传输量,节省了备份空间。

Rabin指纹算法在重复数据检测中的应用研究

Rabin指纹算法计算效率高、随机性好,可将数据更改对连续指纹序列的影响限制在局部范围内,广泛应用于重复数据检测领域。分析了Rabin指纹在有限域GF(2n)上的运算原理,得出滑动窗口移动时定长字符序列的数字指纹快速计算公式。用伪代码描述了Rabin指纹算法在重复数据检测中的应用,并用VC++语言进行了算法实现,在普通计算机上提取Word文档、程序源代码和BMP图像等三类文件作为测试数据集,测试结果表明算法是有效的。

一种基于核心词相似度的重复数据检测框架构建

针对数据清洗过程中的重复数据问题,以企业名称的相似重复度检查为例,提出一种利用核心词相似计算的重复数据检测框架构建。通过对相似重复数据进行分词程序处理和特征属性字典映射,提取核心词,再对核心词作相似度计算,所得结果加权求和得出相似度,以相似度阈值来判别是否重复。实验表明,该框架可有效用于重复数据检测,具有工程实用性。

基于内容的重复数据删除技术的研究

随着企业数据信息量的不断地增加,海量数据信息的存储和不断备份已经给企业的存储空间带来了巨大的存储压力;本文分析了当前主要的重复数据检测和删除技术,,并分析了其优缺点。并提出一种基于内容的重复数据删除策略。

基于数据位图的滑动分块算法

网络中相似的数据文件进行同步与存储的过程中,对数据进行分块是检测数据重复的重要步骤之一,在有效地对数据分块的基础上才能更准确地定位数据间的差异部分.就数据分块方法予以分析总结,在滑动分块算法的基础上,重新将数据文件组织成类似位图的排列形式,对数据位图以列向读取数据信息,形成新的数据分块,并计算列向读取数据的分块指纹信息,以列向数据指纹作为补充校正滑动分块算法定位差异数据能力的不足之处,从而获得更精确的数据差异信息.经实验证明,本方法在同源文件的数据重复检测中效果好于相同条件下的滑动分块方法.

高效的两轮远程文件快速同步算法

远程文件快速同步在文件备份与恢复、Web与ftp网站镜像、分发网络、Web访问中具有广泛的应用。提出了一种高效的基于变长分块和定长滑动块相结合的两轮快速文件同步算法——tpsync。同步算法分两轮进行,第一轮利用基于可变分块技术在粗粒度上定位待同步文件的局部变化数据段,第二轮对局部变化数据段采用定长滑动切块技术在细粒度上查找出差异数据,最终通过两轮数据交互实现文件的同步。将tpsync与传统的单轮同步算法rsync进行了对比实验,通过对文本、二进制和数据库三种文件类型相似版本之间的同步实验,结果表明tpsync在平均同步时间和网络传输数据量两个方面均优于rsync。