基于壓縮近鄰的查重元數據去冗算法設計

姚文斌，葉鵬迪，李小勇，常靜坤

(1.北京郵電大學 智能通信軟件與多媒體北京市重點實驗室，北京 100876；2.北京郵電大學 計算機學院，北京 100876；3.中國鐵道科學研究院 機車車輛研究所，北京 100081；4.北京郵電大學 可信分布式計算與服務教育部重點實驗室，北京 100876)

1 引言

隨著信息量的爆炸式增長，數據占用空間及帶寬越來越大，企業面臨的快速備份和恢復的時間點越來越多，管理、保存、傳輸數據的成本及數據中心空間和電源的耗費也變得越來越昂貴。研究發現，應用系統所保存的數據，高達60%是冗余的，而且隨著時間的推移會變得越來越嚴重，重復數據刪除技術受到越來越多的關注。

常用的基于塊的重復數據刪除算法將數據切分成定長或可變長的數據塊，并計算每個數據塊的散列值作為數據塊指紋，擁有相同指紋的數據塊即被認為是重復的。這種基于塊的重復數據刪除算法對那些變化緩慢、尤其是修改較少的備份數據具有較好的效果。然而隨著數據集的增大，數據塊指紋等元數據信息會迅速超過內存容量，并且由于散列算法的天然隨機性，很難對這些指紋實現有效的緩存，容易造成頻繁訪問磁盤、降低重復數據刪除的性能。

為了解決數據塊指紋檢索過程中面臨磁盤瓶頸問題，DDFS[1]、Sparse Indexing[2]提出通過利用備份數據流中的數據塊局部性特征來構建內存中的查重索引，借此提高塊指紋檢索的命中率，減少磁盤操作。Extreme Binning[3]、Silo[4]和重復數據刪除系統[5～7]通過比較數據對象之間的相似性，將與待去重數據對象較為相似的數據對象的塊指紋數據讀入內存來構建查重索引，在數據局部性特征較少的情況下，也能解決指紋檢索面臨磁盤瓶頸問題。然而，常用的相似數據檢測算法如 shingle detection[8]、Bloom filter[9]都是利用較小的數據片段來代表原始數據對象以實現文件間的相似性檢測，這些片段的長度與數據對象大小相關，在大文件較多的環境下，所產生的較長的數據片段會加重存儲資源開銷。

CDFS[10]基于定長的traits[11]指紋來計算數據對象之間的相似性。Simdedup[12]基于simhash[13]算法，用simhash指紋值來代表原始數據對象，通過比較simhash指紋值來計算數據對象之間的相似性，并基于相似數據對象的塊指紋信息來構建查重緩存，減少磁盤讀寫次數，由于simhash指紋值的長度固定且極小，因此可以將大量數據對象的指紋索引保存在內存中作為相似索引，實現在保持較少的額外系統資源開銷的基礎上，提高重復數據刪除效率。

然而，每個重復數據刪除系統都需要額外的空間來存儲刪重過程中產生元數據信息。例如清單文件，其中保存著包含數據塊指紋值及指向該數據塊所在的磁盤存儲位置的指針的數據塊描述符。通過這些清單文件，順序讀取數據塊描述符，同時加載并串聯描述符所指向的數據塊，便可以重構數據內容。這些數據塊描述符和標準文件系統中的數據塊指針的不同之處就是大小的不同，一般文件系統中的數據塊指針都是8 byte，而重復數據刪除系統中的文件描述符一般至少是20 byte。

現有的對重復數據刪除技術的研究往往會忽略這些元數據信息，認為這些文件一般不會成為系統吞吐量的性能瓶頸。然而，隨著數據集的增加，元數據也會隨之增長，并會占用大量的存儲空間。在重復數據刪除技術的幫助下，存儲數據所需的磁盤空間隨時間緩慢增長，如Zhu等[1]通過應用重復數據刪除技術，在每天備份的環境下，對數據達到了近40:1的壓縮比，數據對存儲空間的需求逐步趨緩。而清單數據等元數據信息卻會隨著去重次數的增加而穩步增長。假設一個數據塊大小為4 KB，那么1 TB的數據就至少需要5 GB的空間來存儲這些清單文件。在備份系統環境下，假如每周執行一次全備份，且保留期為52周，那么對于20 TB的備份數據來說，就會產生至少5 TB的清單數據。因此，在海量數據環境下，保存這些元數據信息將會產生巨大的額外存儲資源開銷。

Simdedup這類基于相似性的重復數據刪除算法對每個已去重數據對象都會產生查重元數據，供以后的重復數據刪除操作使用，由于數據對象之間存在較高的相似性，那么，所產生的清單文件等元數據也會包含大量的相似數據，增加了存儲資源開銷。此外，隨著數據集持續增大，用于檢測數據相似性的相似索引的數據量也會不斷增加并最終導致索引過大以致于難以存放在內存中，影響相似數據檢索的效率，進而影響重復數據刪除效率。在重復數據刪除過程中，使用更大的平均數據塊固然能夠減少數據塊數量，降低清單文件的大小，然而，這種方法會導致重復數據刪除率的下降[14～16]。隨著人們對數據資源的愈發重視，全備份的時間間隔越來越短，且數據保存周期越來越長，清單文件等元數據信息的壓縮已經成為重復數據刪除系統中不容忽視的環節。

常用的元數據壓縮技術中，Zero-Chunk壓縮技術[17,18]只能通過對內容全是0的數據塊給予較短的編碼，來間接對元數據進行壓縮，無法處理其他類型數據塊。基于重復序列的壓縮技術[19～21]只能通過合并重復序列來間接降低元數據大小，無法應對實際環境中，數據塊本身存在冗余，但序列相對較亂的情況。基于統計的壓縮技術[14,22]除了維護數據塊使用率索引外，還需要維護額外的編碼索引，該索引的存放位置是一個需要權衡的問題，如果存儲在內存中，固然會提高訪問速度，但卻會限制編碼的數量，如果存儲在磁盤上，編碼的數量不會有太多限制，但卻會需要額外的I/O操作。因此，在不對重復數據刪除比造成太大影響的前提下，消除查重元數據集中重復度較高的樣本，降低元數據集的數量，使在海量數據環境下，依然維持較低的系統資源開銷，是亟待解決的問題。

本文在Simdedup的基礎上，基于壓縮近鄰[23]的思想，提出了查重元數據的去冗算法Dedup2，在維持重復數據刪除比的同時，可以有效降低用于查重的數據量，使資源開銷保持在一個較低的位置。

2 Dedup2設計思路

Simdedup進行重復數據刪除操作時，由于數據段之間存在較高的相似性，那么，所產生的元數據信息中也必然包含大量的相似數據。

因此，Simdedup中元數據壓縮面臨的問題的描述如圖1所示。圖中的每個點都表示一個對應的數據段，2個數據段距離的遠近表示兩者之間相似度的高低，那么按照兩兩之間的相似性，可以對數據段進行聚類，最后獲得k個類，圖1所示為k=3的情況。由于類中的數據段擁有較高的相似性，那么可以合并相似度高的數據段的清單文件，消除其中的重復數據塊指紋描述符，以減少清單文件大小。

圖1 問題描述

然而，單純通過聚類的方法無法處理相似索引SFIndex，該索引數據量的增加依然會給系統帶來較大的負擔，因此需要針對各個類中數據對象的重要性，消除SFIndex中對重復數據刪除率貢獻相對較小的數據段的指紋。

對于一個新的數據段來說，基于Simdedup算法，其相似特征會出現2種情況，分別如圖1中的黑點S1和S2所示。其中，黑點S1表示該數據段在平面中的位置處于 3個類邊界的外部，其最相似數據段就是與其距離最近的分屬于不同類別幾個白點，這些白點都在類的邊界部位；黑點S2表示該數據段在平面中的位置處于類的內部，其最相似數據段就是與其距離最近的同一類中的幾個白點，由于同類中數據對象相似度較高，所以選擇類邊界的數據段來構建查重緩存，也能提供較好的重復數據刪除率。

因此，消除 Simdedup元數據中處于類中心位置的數據段信息，盡可能保留類邊界位置的數據段信息，便能夠實現元數據的壓縮，并縮小相似索引SFIndex，使之能夠完整存放于內存中，提高重復數據刪除效率，同時維持較低的系統資源開銷。

壓縮近鄰（CNN, condensed nearest neighbor rule）算法主要用于尋找樣本的一致子集。對于一個集合E的一個子集E'，如果利用最近鄰算法（1-NN），E'中樣本可完全正確地分類E中的樣本，那么E'就是集合E的一致子集。從集合E中創建一致子集E'時，首先將所有少數類中的樣本以及隨機選取的一個多數類中的樣本加入E'中進行初始化。然后用E'中的樣本以最近鄰算法（1-NN）對E中樣本分類，將所有錯分的樣本加入到E'中。

壓縮近鄰算法保留了多數類中邊界附近的樣本，同時去掉了多數類中遠離邊界的樣本，使一致子集在保留最少量樣本的條件下，仍能對原有全部樣本用最近鄰法正確分類，那么也就能夠對待識別樣本進行分類，并保持正常識別率。因此，其設計思想和 Simdedup消除相似度較高的元數據，降低查重元數據大小后，仍需保持相近重復數據刪除率的需求是等同的。

基于壓縮近鄰的思想，從相似度過高的元數據對重復數據刪除率影響有限的角度出發，提出了查重元數據去冗算法Dedup2，首先對查重數據集進行聚類，然后利用壓縮近鄰算法獲得查重子集，并基于該查重子集消除相似度較高的元數據，進而降低查重索引大小。消除相似度較高的元數據，在維持重復數據刪除率的同時，可以有效降低元數據的數量，進一步降低系統資源開銷。

3 Dedup2系統架構

重復數據刪除算法的系統整體結構如圖2所示。Simdedup中查重所需要的元數據信息數據被分成 2個索引分別保存，分別是simhash指紋索引（SFIndex）和數據塊指紋索引（CFIndex）。其中，SFIndex保存所有的數據段的simhash指紋，而每個數據段所包含的所有數據塊的指紋值將存儲在磁盤的一個清單文件中，這些清單文件信息則保存在CFIndex里面。由于Simdedup對每個已去重的數據對象都會產生這2種元數據信息，并保存在查重索引中，因此，隨著數據集持續增大，查重索引的數據量也會不斷增加，最終必然導致查重索引無法有效存放在內存中。

圖2 系統結構

Dedup2通過離線處理的方式對查重的元數據信息進行周期性去冗，獲得較小的查重子集。通過消除SFIndex中冗余度較高的元素，可以獲得較小的 simhash指紋子索引 Sub-SFIndex。同時，合并CFIndex中冗余度較高的清單文件，可以獲得較小的清單文件子索引Sub-CFIndex。

對一個數據對象作重復數據刪除操作時，每個數據段都利用可變長分塊算法進行切塊，并利用SHA-1算法計算該數據段所包含數據塊的指紋值。基于所得到的數據塊，可以計算得到每個數據段的simhash指紋。若用于構建內存中數據塊指紋索引的數據段個數設為w，那么通過相似性檢索，比較該指紋和Sub-SFIndex中的其他指紋，可以按照相似度的高低，獲得與待去重數據段最相似的w個數據段。基于這些數據段，便可以通過 Sub-CFIndex檢索清單文件，獲得各數據段對應的塊指紋信息，進而將這些指紋值讀到內存中，構建查重緩存。最后，比對新數據段的指紋值和查重緩存中的指紋值，就可以消除重復的數據塊。

Dedup2能夠消除查重元數據中的重復數據，大大降低查重索引的大小，從而使查重索引能更好地存放在內存中，減少磁盤訪問，保證數據塊指紋檢索速度和較低的系統資源開銷，同時，保持相似的重復數據刪除比。

4 Dedup2算法描述

Dedup2基于壓縮近鄰的思想，以消除元數據中的冗余信息，獲取精簡的查重子集為目的，整個算法流程如圖3所示，可以分為聚類階段和去冗階段2個階段。該方法首先將查重數據集聚成k類{C1,C2, …,Ck}，從每一類別樣本中各隨機選擇一個樣本以構成初始子集，然后按最近鄰原則用該子集對剩余訓練集分類，并將誤分樣本加入查重子集，遍歷整個查重數據集后，便可獲得所需查重子集。

圖3 Dedup2流程

基于該查重子集，消除元數據中對重復數據刪除率影響有限的樣本，進而降低元數據的大小，從而使simhash指紋索引能更好地存放在內存中，減少磁盤訪問，保證數據塊指紋檢索速度和較低的系統資源開銷，同時，保持相似的重復數據刪除比。下面對Dedup2算法的聚類階段和去冗階段分別作詳細描述。

4.1 聚類階段

由于在使用壓縮近鄰算法前需要對各個元數據進行歸類，同時因為元數據的主要指標是simhash值，且無法通過k-means聚類算法對simhash值計算歐氏距離，所以需通過k中心點聚類算法進行歸類。partitioning around medoids (PAM)算法是較常用的k中心點聚類算法，具有數據頑健性強、聚類結果與輸入順序無關以及對小的數據集聚類效果明顯等特點。

為了后續描述清晰，對后續所用符號進行統一定義：定義待查重數據的simhash指紋集合為S={s1,s2, …,sn}；定義聚類前的簇為C={C1,C2, …,Ck}，聚類過程完成后的簇為C'={C1',C2', …,Ck'}；定義2個相似數據段之間的距離度量為dist(si，sj)，2個simhash指紋值的海明距離為Hamming(si，sj)。

本文選用 PAM 算法對元數據進行聚類，以SFIndex中所保存的 simhash指紋值信息來表示一個數據對象，獲得查重數據的指紋集合S={s1,s2, …,sn}。然后，對集合S中的數據對象進行聚類，將數據段分為k類C'={C1',C2', …,Ck'}。

2個相似數據段之間的距離度量表示為兩者simhash指紋值的海明距離，即

所以，整個聚類過程可以描述如下。

1) 從S中任意選擇k個代表對象{m1,m2, …,mk}作為初始的中心點。

2) 指派每個剩余對象給離它最近的中心點所代表的簇C={C1,C2, …,Ck}。

3) 對于每一個簇Ci，i∈{1, 2, …,k}，遍歷簇中的li個非中心點對象sj。

a) 計算用sj代替中心點mi的總代價

b) 選擇總代價最小的那個對象作為新的中心點；

4) 重復2)，3)，直到k個中心點不再發生變化。

最終所獲得的k個簇C'={C1',C2', …,Ck'}，就是所需要的k類相似數據段。

4.2 去冗階段

去冗階段利用壓縮近鄰算法，消除相似度過高的元數據。這里定義壓縮后的查重子集S'={s1',s2', …,sv'}。去冗余階段的過程可以描述如下。

1) 同樣以數據段的simhash指紋值指代各個數據段，獲取SFIndex中的所有數據段simhash指紋集合S={s1,s2, …,sn}。

2) 對集合S設置2個存儲器store和grabbag。

3) 將S的所有樣本放入grabbag中。

4) 從grabbag中隨機取一個數據段simhash指紋s1，放入store。

5) 從grabbag中隨機取出一個數據段simhash指紋sk，用store中的simhash指紋做參考集。

a) 采用近鄰法對sk進行分類，從store中找到一個與sk最近的snb，若snb∈Ci，且sk∈Ci，i∈{1,2, …,k}，則認為分類正確，刪除sk；

b) 否則，sk作為新的一個類別放入store中。

6) 對grabbag中所有樣本進行步驟5)的操作，直到grabbag為空。

7) 此時，store中存放的就是壓縮后的查重子集S'={s1',s2', …,sv'}。根據查重子集S'中的元素，通過消除SFIndex中冗余度較高的元素，同時，合并CFIndex中冗余度較高的cfs清單文件，以實現對元數據進行壓縮，進而獲得新的Sub-SFIndex和Sub-CFIndex。

5 實驗分析

為了驗證Dedup2算法的有效性，利用一臺計算機作為平臺進行了一系列的實驗，其配置如下：CPU為 Intel Core Duo 2.93 GHz，內存為2 GB，磁盤為SATA 5 600轉。在此實驗平臺上利用Java對算法進行了編碼實現，利用Linux源碼包作為待去重數據，對查重數據的去冗效果，讓 Simdedup重復數據刪除算法分別運行在原查重數據集和通過Dedup2產生的查重子集上，從元數據去重比和重復數據刪除比這2個方面進行了對比實驗。

5.1 元數據去冗分析

實驗通過查重索引去重比，即已消除的冗余數據占原查重數據集的比重，來驗證Dedup2對查重數據集的去冗效果。在不同聚類個數k的條件下，在2個數據集中進行實驗，獲得的元數據去重比如圖4所示。其中數據集1包含40 GB的Linux源碼包，數據集2中包含80 GB的Linux源碼包。

圖4 查重子集占原查重數據的比重

由實驗結果可見，總體來看，Dedup2對原查重數據集的去冗效果可以達到50%以上。聚類個數k的越小，最后產生查重子集的也越小，但彼此間的差距并不大。這是由于聚類個數k越大，那么聚類得到的類別也越多，那么在去冗階段采用近鄰法對某個樣本進行分類時，尤其是那些位于2個類邊界上的樣本，發生錯分的概率也會相應增加，因此，該樣本就會被保留下來，進而影響了去冗效果。

此外k=8去重比相對k=10的時候要高一點。這是由于PAM算法對初始中心是隨機選擇的，聚類結果會隨著初始點選擇的變化而改變，容易陷入局部最優的情況，進而會影響最后的聚類效果。而壓縮近鄰算法基于聚類的結果運行，那么去冗效果也相應的會受到影響。k=8與k=10的類別個數相差不大，就比較容易發生這種因為聚類效果的差異，而導致聚類個數k的較小，但最后冗余數據量也較少的情況。但從大趨勢來看，例如比較k=5、k=10以及k=15這三者，還是能清晰地得出聚類個數k越小，消除的冗余數據量越高的結論。

此外，還可以發現當數據集增大時，最后產生查重子集的也越小。這說明數據集越大，數據中的冗余數據越多，便越能產生更好的去冗效果。

5.2 重復數據刪除比分析

重復數據刪除比的實驗在數據集1上進行。在對新數據段執行重復數據刪除操作時，用于構建內存中數據塊指紋索引的數據段個數w越多，那么指紋索引中所包含的已存儲數據塊指紋信息也越多，便越能找出重復數據。

在用于構建查重緩存的最相似數據段數量w=3，而聚類個數k不同的條件下產生多個查重子集，基于這些查重子集和原始查重數據集，分別對數據對象完成去重操作的重復數據刪除率對比結果如圖5所示。從實驗結果可以看出聚類個數k不同對重復數據刪除比沒有特定的影響。此外，圖中重復數據刪除比最低的是基于k=15時獲取的查重子集所獲得，為60.3%；而重復數據刪除比最高的則是基于原始查重數據集所獲得，為61.4%，該結果說明雖然查重子集的大小僅為原始查重數據集的一半不到，但依然能夠獲得近似的重復數據刪除比，進而證明了Dedup2的有效性。

在所用的查重子集為聚類個數k=5時生成，而用于構建查重緩存的最相似數據段數量w不同的條件下，基于該查重子集和原始查重索引，分別對數據對象完成去重操作后的重復數據刪除比對比結果如圖6所示。對比結果說明隨著用于構建查重緩存的最相似數據段數量w增加，利用查重子集進行重復數據刪除操作時，重復數據刪除比也會逐步升高，w=3之前的上升幅度較高，之后仍然會緩慢上升。而當利用原查重索引進行重復數據刪除操作時，同樣w=3之前的上升幅度較高，然而在w=5之后，重復數據刪除比則基本停止上升。這便說明了原查重索引中，w=5之后獲得的查重數據與之前的數據重復度過高，所以雖然構建查重緩存的最相似數據段數量w增加了，但對重復數據刪除比卻沒有幫助。這也證明了Dedup2元數據去冗的有效性。

圖5 k不同條件下的重復數據刪除比（w=3）

圖6 w不同條件下的重復數據刪除比

6 結束語

本文提出一種基于壓縮近鄰的查重元數據去冗算法Dedup2，該算法定期對用于查重的元數據集進行聚類，并在此基礎上利用壓縮近鄰算法去除查重元數據中的冗余數據，以獲得精簡的查重子集，基于該子集消除相似度較高的元數據，進而降低查重索引大小。結合 Simdedup重復數據刪除系統，可以基于文件相似性獲取子集中與待去重數據對象相似度高的索引數據構成查重緩存，以完成重復數據刪除操作。實驗結果證明，Dedup2可以在保持近似的重復數據刪除比的前提下，有效消除查重元數據中的冗余信息，降低查重索引的大小。

[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.