Spectral Bloom Filter (1)

Bloom filter将集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）将位數組中的每一位擴充為一個counter，進而支援了元素的删除操作。一旦位擴充成了counter，每一個counter就不僅能表示這一位址有無映射，還能表示映射的個數。這一擴充使得存儲的資料包含了更多資訊，然而遺憾的是，CBF僅僅利用這個擴充支援了删除操作，并沒有将資訊中蘊含的潛力完全挖掘出來。毫無疑問，Spectral Bloom Filter（SBF）的提出者就看到了這種潛力。

标準的bloom filter和CBF解決的隻是集合元素的membership問題，即判斷一個元素是否屬于某個集合。但有時我們不但想知道集合中是否存在一個元素，我們還想知道這個元素在集合中的出現次數。例如在一些資料流（data stream）應用中，我們關心的也許不是一個資料元素是否屬于某個集合，而是它的出現頻率。很自然地，我們希望能從counter中得到這些資訊。但是，counter反映的隻是映射數，如何将其與集合元素的出現次數關聯呢？

在CBF中加入一個元素時，k個哈希位置的counter都要加1。也就是說，如果不考慮碰撞（collision），出現次數為n的元素對應的k個counter的值都為n。即使考慮到碰撞的因素，隻要k個位置不全出現碰撞，k個counter中的最小值仍是n。令元素x對應的k個counter的最小值為mx，x的出現頻率為fx，從上面的分析我們不難看出，fx ≠ mx的機率和标準bloom filter的false positive機率相同，因為二者出現的充要條件都是k個哈希位置同時出現碰撞。

上面這個結果其實就是SBF的理論基礎。SBF擴充了CBF，使得使用者不但可以進行membership query，還可以查詢集合元素的出現頻率。在查詢元素x的出現頻率時，SBF傳回mx，出錯的機率和false positive rate相同。注意，由于fx ≤ mx，是以查詢的結果即使不準，也可以得到一個上界，而且這個上界和實際值fx一般情況下不會相差太遠。

到現在為止講的都是概念，我們還沒有看到SBF和CBF在構造上有什麼不同。當然，如果不改變CBF就可以加入新的feature，那最好不過了，可惜事情沒有這麼簡單。CBF的counter在隻支援membership query的時候，4位就夠了，如果想要支援元素的出現頻率查詢，4位就遠遠不夠。由于元素有可能成百上千次重複出現，而且完全沒法預測，是以SBF的counter必須能夠動态伸縮。下一次我們就來讨論SBF如何實作counter的存儲。