Page 441 - 《软件学报》2025年第7期

3362 软件学报 2025 年第 36 卷第 7 期

外, 为了支持高速的插入操作, Fu 等人 [21] 提出了垂直布谷鸟过滤器, 通过给每个元素赋予更多的候选位置减少了
布谷鸟哈希表中的重插入操作, 从而提高插入性能. Reviriego 等人 [7] 提出了完美布谷鸟过滤器使得布谷鸟过滤器
在使用一定额外空间的条件下完全避免了误判. 在动态场景下, Mitzenmacher 等人 [28] 提出了自适应布谷鸟过滤器,
可以动态地修改误判元素的指纹, 避免指纹冲突造成误判. 在处理有明显分布特征的数据集时, Kraska 等人 [29] 提
出可以利用机器学习技术显著降低过滤器所需要的空间. 基于这个基本想法, 为了进一步降低过滤器的误判率,
PLBF [30] 和 SF [31] 陆续被提出. 需要注意的是, 这些学习型过滤器只能在有明显分布的数据上才能发挥作用, 在随机
性较大的数据集上误判率会急剧上升, 甚至弱于标准布谷鸟过滤器.
第 2 类变种主要是为了支持动态扩容, 即在动态场景下数据动态增删时调整过滤器空间. 首先, Chen 等人 [22]
提出了动态布谷鸟过滤器 DCF. DCF 由多个相同结构的子布谷鸟过滤器组成, 并且可以动态增加或减少子布谷鸟
过滤器来适应工作负载的动态变化. 此外, Luo 等人 [32] 利用一致性哈希技术设计了索引独立布谷鸟过滤器 I2CF.
I2CF 借用了一致性哈希函数的思想, 全局维护一个一致性哈希环, 并为每个元素分配 k 个候选桶, 从而使得桶的
总数可以动态地增加或减少. 为了进一步减轻扩容导致的额外开销, Zhang 等人 [20] 提出了对数动态布谷鸟过滤器
LDCF. LDCF 设计了一种可扩展的多级树结构来连接多个子布谷鸟过滤器, 并进一步地根据元素指纹的前缀来定
位元素在树结构的具体位置, 从而将查询复杂度从线性降低到对数复杂度. Fu 等人 [33] 拓展了 I2CF 等人的思想, 基
于跳跃一致性哈希提出了跳跃滤波器, 可以同时实现随数据基数线性增长的空间开销以及常数级数据访问时开
销. 进一步地, Wang 等人 [26] 为了支持更为细粒度的扩容, 借用线性哈希函数的思想细粒度地扩展布谷鸟过滤器的
空间, 并提出了 Bamboo 过滤器.
第 3 类变种主要是基于布谷鸟过滤器拓展支持更多的查询功能. Ting 等人 [14] 提出了条件布谷鸟过滤器, 用以
大幅减少计算数据库中连接操作时需要处理的数据量. Gu 等人 [15] 基于布谷鸟过滤器构建了一个数据摘要, 用来辅
助估计云计算系统中动态负载下需要的缓存大小.

2 代价敏感的指纹可变哈希布谷鸟过滤器设计

在进入具体的技术细节解释之前, 本文首先定义需要研究的问题.

2.1 问题定义
N
代价敏感近似集合成员查询问题. 给定集合 P 和集合 , 且 N ∩ P = ∅, 在近似地判定某个元素在集合 P 和集
C(x), 要求最小化总体的误判代价. 为了
合 N 中时, 如果集合 N 中某个元素 x 如果被误判在 P 中, 其误判的代价为
∑
F(x)·C(x), 其中
解决该问题, 本文提出构建一个过滤器 F 近似回答某个元素是否在 P 中, 最小化误判的代价
x∈N
F(x) = 1 表示过滤器 F 判定元素 x 在集合 P 中. 需要强调的是, 这里的“代价敏感”是指在解决近似集合成员查询问
题时, 在考虑元素有误判代价的情况下, 调整过滤器结构, 从而最小化总体的误判代价. 表 1 列出了本文用到的
符号.

表 1 指纹可变哈希布谷鸟过滤器 VHCF 中参数含义

参数 含义 参数 含义
P 需要存储在过滤器内的元素集合 b VHCF内包含的哈希桶个数
N 需要避免误判的元素 c VHCF单个哈希桶可存储的指纹单元数
C(x) 元素 x 的误判代价 d VHCF单个哈希桶内哈希索引单元比特数
f(x) 元素 x 的指纹哈希函数 e VHCF单个哈希桶内指纹单元的指纹长度

P 和集合 ; (2) 如何获取误判代价
N
上述问题定义中涉及两个关键步骤还需要进一步说明: (1) 如何划分集合
N
C(x). 首先, 我们关注如何划分集合 P 和集合 . 需要强调的是, 集合 P 和集合 N 是根据具体应用的实际需求自然
N 对应不需
划分的. 为了更好地说明, 我们以无状态网络多播应用为例, 集合 P 对应需要进行广播的节点, 而集合
要广播的节点. 集合 P 和集合 N 的划分完全取决于网络广播应用的需求. 同样, 在网络黑名单过滤的例子中, 集合