Shifting Bloom Filter For Membership Query

算法实现

符号说明

Symbol	Desc
$m$	BF大小
$n$	BF中元素个数
$k$	BF中哈希函数个数
$k_{opt}$	自定义的k
$S$	一个集合
$e$	一个集合里面的元素
$u$	一个集合里面的元素
$h_i(s)$	s 的 第 i 个哈希值
$FP$	误判
$FPR$	误判率
$f$	BF的误判比例
$p^{\prime }$	添加所有 n 个元素后 某个比特为0的概率
$BF$	标准BF实现
$iBF$	独立BF，对于每个集合单独创建一个BF
$ShBF$	Shifting BF
$ShB{F}_M$	用于成员查询的ShBF
$ShB{F}_A$	用于关系查询的ShBF
$ShB{F}_{\times }$	用于计数查询的ShBF
$Qps$	每秒查询数量
multi-set	允许重复的集合
$o(.)$	偏移量
$w$	机器字长
$\bar{w}$	最大偏移量
$c$	某个元素最大出现次数

构建阶段

构建分为三步

1. 构建 $\frac{k}{2}+1$ 个独立均匀分布的哈希函数，包含 $m$ 个比特的数组 $B$
2. 冲集合 $S$ 中读取 元素 $e$，
   1. 使用前 $\frac{k}{2}$ 个哈希函数计算并存储存在信息：$h_1(e)\%m,h_2(e)\%m,\cdots ,h_{\frac{k}{2}}(e)\%m$
   2. 使用第 $\frac{k}{2}+1$ 个哈希函数计算偏移信息：$o(e)=h_{\frac{k}{2}+1}(e)\%(\bar{w}-1)+1$
3. 将偏移信息 $[h_1(e)+o(e)]\%m,[h_2(e)+o(e)]\%m,\cdots ,[h_{\frac{k}{2}}(e)+o(e)]\%m$ 设为1

如何选择合适的 $\bar{W}$

我们需要一个合适的 $\bar{W}$ 让我们可以同时处理 $h_i(e)\%m$ 以及 $[h_i(e)\%m]+o(e)$。

注意，像x86平台的CPU可以从任何字节访问数据，不需要对其，也不需要在同一个 WORD 中

比如说，$B[h_i(e)\%m]$ 是某字节的第 $j$ 个元素，为了同时访问，我们需要保证 $j-1+\bar{w}$ 能被一次访问，即 $j-1+\bar{w}\le w$ ，j最大为时 $\bar{w}$ 的最大值最小为 $w-7$，那么$\bar{w}\le w-7$

大概长这样