Spectral Bloom Filter

文章来源：http://blog.csdn.net/jiaomeng/archive/2007/03/19/1534238.aspx

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的存储。

上一节说到SBF对counter的存储。为实现counter的高效存储，我们先简化问题，来看最少需要多少位才能存储所有的counter。假设SBF要表示M个元素的集合（可能包含重复元素），counter数组的长度为m（对应着bloom filter的位数组），显然所有counter需要的最少位数N为

 

其中Ci表示counter数组中第i个counter的大小，即哈希函数映射到第i位的次数。用N位存储counter，其实相当于把所有的counter化成二进制位串然后连在一起。这样当然占用的位数最少，但如何访问长度不一的counter是个大问题。不管怎么样，在不考虑增删操作的情况下，我们想要达到的目标就是在保证查询操作快速的基础上，使得存储位数尽量接近N。

 

SBF并没有发明什么异乎寻常的高超技巧，和你大概能想到的一样，它构建了一套索引结构。首先SBF将N位的基本位串分成m/logN段，每一段包含logN个counter，然后将每一段的offset记下来。由于offset要占用logN位，所以记录子串offset的数组（论文中叫Coarse Vector）总长度为m位。

  

有了Coarse Vector，我们就可以随机访问任何一个子串了。这时我们有两种选择，要么把子串继续分成子段，要么将子串中所有counter的offset记下来（即上图中的OV，Offset Vector）。子串有长有短，但所含counter个数相同，也就是记录counter的offset数组长度相同，这就意味着把长子串用来记录offset比较划算。SBF规定子串长度超过log³N位的，直接用offset数组记录counter位置，否则再继续分。N位基本位串中最多有N/log³N个长度不超过log³N的子串，所以在这一层所有的offset数组加起来长度最多为N/log³N × (logN × logN) = N/logN位。

 

长度不超过log³N位的子串，我们将其再分成loglogN段，每一段包含logN/loglogN个counter。由于offset要占用loglog³N = 3loglogN位，所以整个offset数组总长度为3loglogN ×logN/loglogN = 3logN位。这一层所有的offset数组加起来长度最多为m/logN × 3logN ＝ 3m位。

 

并不是子串的每一个子段都用offset数组来存储counter的位置，和前面一样，仍然只记录较长的子段。假设子段长度为T，这里的阀值设为T0 = (loglogN)³，当T > T0时，子段的counter位置用offset数组记录。由于子段包含loglogN个counter，且每一个offset可以用3loglogN位表示，因此offset数组的长度最多为loglogN × 3loglogN ＝ 3(loglogN)² « T。这一层的所有的offset数组长度加起来也不过O(N)。

 

现在就剩了T ≤ T0的情况，这时SBF也不继续分了，而是将所有这类情况存储在一个全局查询表里。关于这个查询表，这里就不多做介绍了，有兴趣的可以去读一下。总之，在不考虑增删操作的情况下，SBF的counter存储所要达到的目标就是只使用O(N) + O(m)位，构建时间为O(m)。通过上面构建的复杂的索引结构，这个目标是达到了。下一节我们来看增删操作如何在这样的结构上实现。

上一节中，我们介绍到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的优化。

在membership query上，由于SBF和CBF都沿用bloom filter的基本结构，因此很难在membership query上提高查询效率。但在查询元素出现频率（大于1的情况）时，由于SBF采用counter中的最小值来近似表示元素的出现频率，使得各个counter的重要性有所差别，因此CBF将counter一视同仁的做法就有提高的空间。

 

先来看第一种优化算法Minimal Increase。这种算法的思想比较简单，从它的名字大家也能猜出个大概。它的基本思想是：既然在查询元素出现频率时我们只关心counter的最小值，那在增加元素时我们就只增加最小值。如果有多个counter都是最小值，把它们都增加；如果连续加入r个相同的元素，就把最小值（一个或多个counter）加r，其它counter的值或者维持不变，或者设为最小值加r，看哪一个比较大。这种算法是一种聪明的偷工减料：原来增加一个元素时要增加k（哈希函数个数）个counter，现在只需要增加最小值。而counter的增加次数一旦减少，就意味着hashing时碰撞的次数减少，因此查询元素出现频率时出错的可能性也就随之降低。经论文作者证明，Minimal Increase使查询错误率降低了k倍。

 

当然，偷工减料不可能只有好处。Minimal Increase最大的弊端就是不支持删除操作。很明显，由于增加元素时增加的counter不确定，因此删除元素时也无从下手。如果将k个counter都减少，就会造成false negative的出现（查询结果表明集合不包含某元素而实际上包含）。由于这个严重的弊端，Minimal Increase的应用前景被大打折扣。

 

下面我们来看一种既支持增删操作又降低查询错误率的算法Recurring Minimum。这种算法的基本思想是：发现有可能出错的情况，然后将它们单独处理。先解释一下什么是recurring minimum。SBF中如果一个元素对应的k个counter中有一个以上都维持最小值，就称它有recurring minimum（RM）。我们发现没有RM（即single minimum）的元素出现查询错误的概率很高，而有RM的元素错误概率很低。因此这种算法将没有RM的元素单独处理，在主SBF之外又增加了一个辅助的SBF，专门用来存储这类元素。由于这类元素所占比例不会太大，因此辅SBF可以只分配较小的空间，比如主SBF的一半大小。

 

采用Recurring Minimum增加元素x时，先将x在主SBF对应的k个counter的值增加，然后再判断这k个counter有没有recurring minimum。如果有，就当什么事都没有发生，直接继续；如果没有，就意味着x出错的概率很大，这时我们将x存储在辅SBF上，counter的值设为x在主SBF对应counter的最小值。删除元素和上面的操作类似，由于主SBF没有受算法的影响，所以不会出现false negative。在查询一个元素时，先看它在主SBF中有没有recurring minimum。如果有，就返回counter的最小值；否则检查辅SBF中的counter最小值，如果大于0就返回这个值，否则返回主SBF的值。

 

由于有recurring minimum的情况本来出错概率就很小，而没有recurring minimum的情况又单独处理，也大大降低了出错概率，所以整个算法的错误率得以降低。Recurring Minimum算法的错误率虽然不及Minimum Increase，但比原来的错误率要好很多，可以说是用更多的空间换取了错误率的大幅降低。