基于Bloom Filter的重復(fù)數(shù)據(jù)刪除技術(shù)研究與應(yīng)用.pdf

1、在大數(shù)據(jù)時代，每天都會產(chǎn)生大量的數(shù)據(jù)，而在這些產(chǎn)生的數(shù)據(jù)中有很大部分是重復(fù)數(shù)據(jù)，如何對海量重復(fù)數(shù)據(jù)進行快速檢索越來越受到人們的關(guān)注。
　　Bloom Filter作為一種輕量級的數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)的檢索中受到了廣泛的應(yīng)用，但是Bloom Filter也存在著不足之處，由于其是一種概率型數(shù)據(jù)結(jié)構(gòu)，故在數(shù)據(jù)的檢索中存在誤判的發(fā)生，同時Bloom Filter只針對于靜態(tài)數(shù)據(jù)集的表示與查找，而不能進行動態(tài)擴展存儲。近年來，針對Bloom F

2、ilter以上所提到的不足之處存在多種改進，其中拆分Bloom Filter和動態(tài)Bloom Filter實現(xiàn)了元素的動態(tài)增長存儲，從而解決了Bloom Filter靜態(tài)存儲的問題，并且能夠有效地減少誤判率，但是拆分Bloom Filter和動態(tài)Bloom Filter卻增加了元素的查詢時間開銷。
　　本文根據(jù)當(dāng)前Bloom Filter的動態(tài)存儲以及查詢等問題，提出了多路平衡型矩陣Bloom Filter(Multi-group

3、s Balance Matrix Bloom Filter,M-BMBF),M-BMBF根據(jù)數(shù)據(jù)集合大小建立一個r×m矩陣型Bloom Filter，設(shè)計多個定位哈希函數(shù)將該矩陣Bloom Filter分為多組（多路）以實現(xiàn)平衡插入和高效查詢操作。為減緩Bloom Filter中比特的消耗速度，應(yīng)用一種“最長位匹配”填充方式，新元素的插入將從多路備選Bloom Filter中選擇新置為1比特個數(shù)最少的Bloom Filter中進行。

4、r>　　HDFS是一種開源的分布式文件系統(tǒng)，為了保證文件的可靠性，通常在HDFS中會存儲文件的多個副本，默認(rèn)是3個，當(dāng)用戶每一次向HDFS中上傳同一個文件時，在HDFS中都會保留該文件的多個副本，故在HDFS中存在著大量的重復(fù)數(shù)據(jù)，而HDFS對用戶所上傳的重復(fù)數(shù)據(jù)并沒有做出有效的處理，都將其視為新數(shù)據(jù)寫入系統(tǒng)中，同時還在系統(tǒng)中保留多個副本，導(dǎo)致存儲空間的極大浪費，本文最后在對HDFS進行深入的分析和研究的基礎(chǔ)上，設(shè)計和實現(xiàn)了一個基于M-