相似聚类的二级索引重复数据删除算法  

Secondary Index Deduplication Algorithm Based on Similar Clustering

作　　者：王青松[1] 葛慧 

机构地区：[1]辽宁大学信息学院,沈阳110036

出　　处：《小型微型计算机系统》2017年第12期2797-2801,共5页Journal of Chinese Computer Systems

基　　金：国家社科青年基金项目(13CRK027)资助

摘　　要：针对重复数据删除算法指纹对比I/O瓶颈问题,提出一种基于相似聚类的二级索引重复数据删除算法.首先计算所有数据块的Simhash值,基于Simhash值之间的海明距离,提出一种自适应的相似聚类算法,所有聚类中心信息形成一级索引存放在内存中.然后计算每个类中数据块的MD5值,将其信息形成二级索引存放在聚类中心.当需要进行重复数据块检测时,计算待检测数据块Simhash值到一级索引中所有聚类中心Simhash值的海明距离,并将海明距离最小的类的二级索引调入内存中进行MD5指纹对比.实验结果表明,算法没有误判率,在较大提高了指纹对比速度的同时,每次检测只产生一次I/O操作,具有更高效的性能.Focused on deduplication algorithm of fingerprint comparison I/O bottleneck problem, put forward a secondary index deduplication algorithm based on similar clustering. Firstly calculating all the data blocks＇s Simhash values, based on the Hamming distance between Simhash values,proposes an adaptive similar clustering algorithm,and all clustering centers＇s informations form the primary index stored in memory. Then, calculating data blocks＇s MD5 in each cluster and forming the secondary index stored in clustering center. When need to check blocks,computing the Hamming distance between detectioned block＇s Simhash and all clustering centers＇s Simhash,load the cluster that has the minimum Hamming distance into memory, and comparing MD5 fingerprints. The experimental results show that the algorithm has no false positive rate, at the same time it has considerable improvement in the speed of fingerprint comparison, only one time I/O operation is generated at each detection, hence it has more efficient performance.

关 键 词：重复数据删除 二级索引 相似聚类 Simhash 海明距离 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]