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

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

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

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

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