動態變更查詢優先權的布隆過濾器

Abstract

布隆過濾器是一種節省記憶體空間的資料結構，提供儲存靜態資料集合與集合成員確認的功能。布隆過濾器被運用於許多的領域，例如在於分散式系統的領域，布隆過濾器可被用於系統內同儕之間的訊息交換以節省網路頻寛的使用。以共同合作的網頁代理伺服器而為例，網頁代理伺服器之間會週期性的將目前快取的資料特徵值儲存於布隆過濾器中並互相交換。當網頁代理伺服器收到一筆查詢資料的請求但並沒有快取相關的資料時，則可以藉由查詢布隆過濾器得知哪個同儕具有所需要的資料而向其發出資料請求的封包以避免不必要的封包發送。對於現存的文獻中，於多個布隆過濾器中進行成員確認的方法都是採用循序搜尋的架構。不幸的，多個布隆過濾器的查詢次序是不可被預測，若被查詢的資料是儲存於具有較低查詢優先權的布隆過濾器時，就需要較高的查詢成本。本文針對上述的議題提出了一種能夠節省查詢成本的方法。經由參考時域性的分佈而即時的更新相關的布隆過濾器之查詢優先權，分配給經常被查詢的布隆過濾器較高的查詢優先權，藉以減少不必要的布隆過濾器進行成員確認的成本。對於現存的方法而言，本文所提出的方法至多可以節省40%的搜尋成本。經由不同應用領域的日誌檔驗證得知，本文的方法面對不同傾向的時域性分佈都具有較好的表現。

Bloom Filter is a space-efficient data structure for representing static data set and supporting membership check of the set. Bloom Filter is widely applied to many fields such as distributed systems. Bloom Filter can be used for saving the network bandwidth when interchanging information with peers in a distributed system. For example in cooperative web proxy design, web proxies periodically index their cache data to Bloom Filters and exchange them with each other. A web proxy can check Bloom Filters to find out which proxy cache the web document and send a query directly to that proxy. It can avoid broadcasting requests to all the peers which may not have cached data. To check a membership in multiple set of bloom filters in a dynamic bloom filter, a sequential search order is usually used. Since distribution of web queries usually has temporal locality feature which means there is a very high probability that the recent web query will be queried again in a short future. Therefore to save search cost, we propose a scheme that can dynamically reorder the searching sequence of multiple bloom filters in a dynamic bloom filter. Simulation results show that our scheme on average has 40% better in searching performance comparing with the sequential methods, which is verified via three different trace log files.