在各種各樣的大數(shù)據(jù)應(yīng)用中,高效的近似集合表示和成員判定是至關(guān)重要的。與之前的布隆過(guò)濾器及其變體相比,最新的布谷鳥過(guò)濾器由于其高效的查詢效率和對(duì)集合元素刪除的支持在近似集合表示上展現(xiàn)出強(qiáng)大的優(yōu)勢(shì)。然而布谷鳥過(guò)濾器在元素插入過(guò)程中會(huì)出現(xiàn)嚴(yán)重的性能下降。通過(guò)理論分析和實(shí)驗(yàn)證實(shí),插入性能的急劇下降是因?yàn)椴脊萨B過(guò)濾器在元素插入過(guò)程采用了隨機(jī)選擇策略將元素插入到相應(yīng)的候選桶中。這種隨機(jī)選擇策略會(huì)導(dǎo)致布谷鳥過(guò)濾器中不同桶之間的負(fù)載不均衡,隨著布谷鳥過(guò)濾器變得越來(lái)越滿,這種負(fù)載的不均衡會(huì)變得越來(lái)越明顯,導(dǎo)致后面的元素插入過(guò)程中出現(xiàn)頻繁的重定位,布谷鳥過(guò)濾器的插入性能嚴(yán)重下降。為了解決這一問(wèn)題,提出基于負(fù)載均衡的高效布谷鳥過(guò)濾器利用排隊(duì)論中的重要原理,“兩種選擇的力量（The Power of Two Choices）”來(lái)進(jìn)行元素插入過(guò)程中候選桶位置的選擇。該設(shè)計(jì)實(shí)現(xiàn)了布谷鳥過(guò)濾器桶之間的負(fù)載均衡,降低了插入過(guò)程中的重定位發(fā)生概率。為了證明該設(shè)計(jì)的有效性,將基于負(fù)載均衡的高效布谷鳥過(guò)濾器應(yīng)用于現(xiàn)實(shí)的應(yīng)用中,并使用從現(xiàn)實(shí)系統(tǒng)中收集的大規(guī)模數(shù)據(jù)進(jìn)行實(shí)驗(yàn)來(lái)測(cè)試該設(shè)計(jì)的性能。實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有的布谷鳥過(guò)濾器相... 

【文章來(lái)源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：58 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

指紋負(fù)載分布（i = 445655） 圖 3-2 指紋負(fù)載分布（i = 471870）

過(guò)濾器中當(dāng)前負(fù)載和滿的桶的數(shù)目之間的關(guān)系，所以通過(guò)使用公式（2.12）和公式（2.15）可以得到使用隨機(jī)選擇策略的布谷鳥過(guò)濾器當(dāng)前負(fù)載和重定位次數(shù)期望之間的關(guān)系。同理可以通過(guò)使用公式（2.12）和公式（2.17）得到使用“兩種選擇的力量”策略的布谷鳥過(guò)濾器當(dāng)前負(fù)載和重定位次數(shù)期望之間的關(guān)系。為了更直觀的展示基于負(fù)載均衡的高效布谷鳥過(guò)濾器相對(duì)于原始的布谷鳥過(guò)濾器的優(yōu)越性，本章首先進(jìn)行了數(shù)值分析模擬實(shí)驗(yàn)，分別計(jì)算了當(dāng)前負(fù)載和滿桶數(shù)目之間的數(shù)值解和當(dāng)前負(fù)載和重定位次數(shù)期望之間的數(shù)值解。在模擬實(shí)驗(yàn)中，使用了不同負(fù)載因子下布谷鳥過(guò)濾器中滿桶的數(shù)目和重定位次數(shù)兩個(gè)指標(biāo)來(lái)比較原始和布谷鳥過(guò)濾器和基于負(fù)載均衡的高效布谷鳥過(guò)濾器的性能差異。還比較了當(dāng)負(fù)載因子為 0.8 和 0.9 時(shí)分別使用兩種不同策略的布谷鳥過(guò)濾器中的負(fù)載分布。設(shè)置 m=217和 b=4。為了方便起見(jiàn)，設(shè)置布谷鳥過(guò)濾器的初始負(fù)載 （0 ≤ ≤ ）中 00= 4， 01= 1， 02= 1， 03= 1和 04=圖 3-3 滿桶的數(shù)目 圖 3-4 重定位次數(shù)

過(guò)濾器中當(dāng)前負(fù)載和滿的桶的數(shù)目之間的關(guān)系，所以通過(guò)使用公式（2.12）和公式（2.15）可以得到使用隨機(jī)選擇策略的布谷鳥過(guò)濾器當(dāng)前負(fù)載和重定位次數(shù)期望之間的關(guān)系。同理可以通過(guò)使用公式（2.12）和公式（2.17）得到使用“兩種選擇的力量”策略的布谷鳥過(guò)濾器當(dāng)前負(fù)載和重定位次數(shù)期望之間的關(guān)系。為了更直觀的展示基于負(fù)載均衡的高效布谷鳥過(guò)濾器相對(duì)于原始的布谷鳥過(guò)濾器的優(yōu)越性，本章首先進(jìn)行了數(shù)值分析模擬實(shí)驗(yàn)，分別計(jì)算了當(dāng)前負(fù)載和滿桶數(shù)目之間的數(shù)值解和當(dāng)前負(fù)載和重定位次數(shù)期望之間的數(shù)值解。在模擬實(shí)驗(yàn)中，使用了不同負(fù)載因子下布谷鳥過(guò)濾器中滿桶的數(shù)目和重定位次數(shù)兩個(gè)指標(biāo)來(lái)比較原始和布谷鳥過(guò)濾器和基于負(fù)載均衡的高效布谷鳥過(guò)濾器的性能差異。還比較了當(dāng)負(fù)載因子為 0.8 和 0.9 時(shí)分別使用兩種不同策略的布谷鳥過(guò)濾器中的負(fù)載分布。設(shè)置 m=217和 b=4。為了方便起見(jiàn)，設(shè)置布谷鳥過(guò)濾器的初始負(fù)載 （0 ≤ ≤ ）中 00= 4， 01= 1， 02= 1， 03= 1和 04=圖 3-3 滿桶的數(shù)目 圖 3-4 重定位次數(shù)

【參考文獻(xiàn)】：
期刊論文
[1]一種采用簽名與哈希技術(shù)的云存儲(chǔ)去重方案[J]. 張桂鵬,匡振曦,陳平華.  計(jì)算機(jī)工程與應(yīng)用. 2020(01)
[2]基于排隊(duì)論綜合指標(biāo)評(píng)估的動(dòng)態(tài)負(fù)載均衡算法[J]. 王文博,葉慶衛(wèi),周宇,陸志華.  電信科學(xué). 2018(07)
[3]基于布隆過(guò)濾器所有權(quán)證明的高效安全可去重云存儲(chǔ)方案[J]. 劉竹松,楊張杰.  計(jì)算機(jī)應(yīng)用. 2017(03)
[4]一種基于社交關(guān)系的移動(dòng)緩存替換算法[J]. 邢起源,王菁,閆阿賓,韓燕波.  計(jì)算機(jī)科學(xué). 2016(06)
[5]海量圖片文件存儲(chǔ)去重技術(shù)研究[J]. 孫有軍,張大興.  計(jì)算機(jī)應(yīng)用與軟件. 2014(04)
[6]騷擾電話監(jiān)控系統(tǒng)的研究與設(shè)計(jì)[J]. 殷春祥,朱曉民,彭剛.  計(jì)算機(jī)系統(tǒng)應(yīng)用. 2010(07)
[7]SmartCache:基于興趣的協(xié)作式Web緩存[J]. 陳海濤,盧宇彤,黃遵國(guó).  計(jì)算機(jī)科學(xué). 2008(12)



本文編號(hào)：3271047