一種可擴(kuò)展計(jì)數(shù)布魯姆過(guò)濾器的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、信息的表示和查找是大多數(shù)計(jì)算機(jī)應(yīng)用程序的核心。近年來(lái)，隨著信息技術(shù)的發(fā)展，計(jì)算機(jī)網(wǎng)絡(luò)已經(jīng)成為人類社會(huì)重要的信息基礎(chǔ)設(shè)施，并強(qiáng)力滲透到各個(gè)領(lǐng)域。資源的交互共享促進(jìn)了更多數(shù)據(jù)和信息的產(chǎn)生，隨著計(jì)算機(jī)的飛速發(fā)展，數(shù)據(jù)庫(kù)、網(wǎng)絡(luò)和其他應(yīng)用中的數(shù)據(jù)集合規(guī)模呈幾何增長(zhǎng)。在信息集合變得越來(lái)越大，訪問和表示越來(lái)越困難的情況下，如何表示大數(shù)據(jù)集合，完成大數(shù)據(jù)集合下的查詢成為國(guó)內(nèi)外學(xué)術(shù)界的挑戰(zhàn)性課題。
　　布魯姆過(guò)濾器(Bloom Filter，BF)

2、是一種能夠簡(jiǎn)潔表示靜態(tài)集合并支持集合成員從屬查詢的數(shù)據(jù)結(jié)構(gòu)。它采用一個(gè)位串表示數(shù)據(jù)集，以可接受的誤判率為代價(jià)支持元素的哈希查找。在數(shù)據(jù)庫(kù)、網(wǎng)絡(luò)和分布式系統(tǒng)中，布魯姆過(guò)濾器已經(jīng)得到廣泛應(yīng)用。然而，受限于布魯姆過(guò)濾器的基本屬性，實(shí)際應(yīng)用中必須事先根據(jù)存儲(chǔ)元素的數(shù)量和給定的誤判率來(lái)估計(jì)所需過(guò)濾器的大小，如果達(dá)到過(guò)濾器最大容量后仍需額外存儲(chǔ)元素，那么誤判率就會(huì)增長(zhǎng)，并且標(biāo)準(zhǔn)布魯姆過(guò)濾器只支持靜態(tài)集合的表示，并不支持元素的刪除。因此，隨著數(shù)據(jù)集的

3、動(dòng)態(tài)增長(zhǎng)，并伴隨元素的刪除，傳統(tǒng)布魯姆過(guò)濾器將會(huì)遭遇到難以克服的困難。
　　為此，本文設(shè)計(jì)了一種新型的可擴(kuò)展的計(jì)數(shù)布魯姆過(guò)濾器(Scalable CountingBloom Filter，SCBF)，通過(guò)添加額外的元數(shù)據(jù)來(lái)標(biāo)識(shí)集合中的元素，增強(qiáng)元素和布魯姆過(guò)濾器之間的關(guān)系，準(zhǔn)確判斷元素究竟屬于哪一個(gè)布魯姆過(guò)濾器，不僅支持新元素的插入，還支持已有元素的可靠刪除。主要工作如下:
　　1)實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)展。在計(jì)數(shù)布魯姆過(guò)濾器的基礎(chǔ)上提

4、出一種動(dòng)態(tài)擴(kuò)展方案，通過(guò)創(chuàng)建一個(gè)布魯姆過(guò)濾器的列表，作為一個(gè)大的布魯姆過(guò)濾器，每當(dāng)過(guò)濾器滿載后要更大的容量時(shí)，新建一個(gè)新的過(guò)濾器添加到列表中。同時(shí)，使用一個(gè)縮緊率r控制每個(gè)新添加過(guò)濾器的誤判率，確?？傮w誤判率可控。
　　2)實(shí)現(xiàn)精確刪除。整合布魯姆過(guò)濾器的刪除功能和可擴(kuò)展性。在元素的插入和刪除過(guò)程中，以單調(diào)遞增的序列作為額外添加的標(biāo)識(shí)，將元素歸類。那么就可以通過(guò)元素的標(biāo)識(shí)確定元素的歸屬，從而確保元素可以從正確的過(guò)濾器刪除。