Spectral Bloom Filter (3)

上一節中，我們介紹到SBF将所有counter排成一個位串，counter之間完全不留白隙，然後通過建立索引結構來通路counter。現在我們來擴充這個結構，使之能支援增加和删除操作。

删除操作相對來說比較好處理，因為它不會導緻存儲空間的增加。但是也不能坐視不管，因為大量的删除操作會導緻本該釋放的空間仍然被占用。SBF采取的政策是，單個删除操作隻影響相關的counter，整個存儲結構并不更新，但經過一系列連續的删除操作後，整個存儲結構會被重建。

增加操作稍微麻煩點，因為它意味着原來配置設定的存儲空間不再夠用。SBF采取的應對政策有點像我們平時排工作計劃時留buffer的做法。我們在安排工作時，如果一件事估計需要10天才能做完，我們寫計劃時不會寫成剛好10天，因為事态的發展有太多動态變化的因素。我們會在計劃裡給自己留一點buffer，将10天的工作寫成12天。

SBF處理增加操作時也采取相似的政策，它給原本隻需要N位的基本位串增加єm（є > 0，m為counter個數）位的buffer，以應對将來可能出現的增加操作。SBF将這єm位buffer插入到m個counter之間，每1/є個counter增加1位buffer。當某個counter需要更多位數時，它就找離自己最近的buffer位。如果找到的buffer位就在自己的尾部，就直接用掉它；如果隔了一個或幾個counter，它就将隔的這幾個counter往後“推”，然後使用騰出來的buffer位。最後，counter移動之後，别忘了索引結構也需要更新。

到此為止，SBF的基本結構就介紹完畢。回顧一下，SBF是一種擴充版的counting bloom filter（CBF），它不僅支援membership query，還支援元素在multi-set中的出現頻率查詢。實際上，前者隻是後者的一種特例，membership query無非是元素出現頻率為1的查詢。元素出現頻率用k（哈希函數個數）個counter中的最小值來近似表示。這種近似使得一個元素對應的k個counter中，最小的那個比其它的更有價值。基于這個考慮，論文作者又對SBF的建構過程進行了優化，并給出了兩種優化算法。下一次我們就來讨論SBF的優化。