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

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

VHCF. 相较于 VHCF, HABF 的设计基于布隆过滤器. 在查询过程中, 需要访问多个随机的比特位, 因此 HABF 需
要进行多次哈希计算. 与之不同, VHCF 在查询阶段涉及的是最多 2 个哈希桶, 这导致更少的缓存缺失. 此外, 从获
取哈希函数的效率考虑, 在 VHCF 中获取桶中的指纹生成函数仅需要额外读取一次与桶中指纹一起存储的哈希
索引单元即可完成. 相较之下, HABF 需要查询额外的辅助结构, 以获取每个元素所需的哈希函数, 这一步骤引入
了大量的时间开销. 综合而言, 由于 HABF 在查询过程中可能会引入更多的缓存缺失, 同时需要进行多次复杂的
哈希计算, 以及额外的哈希函数获取步骤, 其吞吐量相较于 VHCF 明显较低.

VHCF CF ACF BF HABF
0.06 0.06 0.05
Weighted FPR 0.04 Weighted FPR 0.04 Weighted FPR 0.03
0.04

0.02
0.02
0.02
0 0 0.01 0
8 9 10 11 8 9 10 11 8 9 10 11
BPK BPK BPK
(a) skewness=0 (b) skewness=0.5 (c) skewness=0.99
图 9 MAWI 数据集上, 不同倾斜程度下, 误判率随每个元素分配的比特数 BPK 变化

VHCF CF ACF BF HABF

100
10 6
Throughput (Mops/s) 10 Latency per key (ns) 10 5

10 4
CAIDA MAWI CAIDA MAWI
(a) 查询吞吐量 (b) 构造时延
图 10 查询吞吐量和构造时延

与此同时, 所有算法的构造时延如图 10(b) 所示. 由于求取最优哈希函数引入的额外操作, VHCF 的构造速度
要慢于两个经典过滤器, 但与自适应过滤器 HABF 基本一致, 远快于 ACF. 实验的所有过滤器中构造速度最快的
是 BF, 这是因为 BF 的插入操作仅仅涉及比特位操作. 综合来看, VHCF 的构造时延平均约为 150 μs, 仍可接受.
5 总 结

本研究提出了一种指纹可变哈希技术, 旨在解决静态场景下的代价敏感集合成员问题. 本文设计了一种指纹
可变哈希布谷鸟过滤器, 并进一步引入了单哈希技术, 以降低指纹可变哈希所带来的额外哈希计算开销, 显著提升
了无状态网络多播等应用场景中的系统性能. 此外, 本文的基本想法是通过利用历史查询信息优化近似索引过滤
器的结构设计, 类似的想法还可以复用在其他系统组件如磁盘索引构建, 缓存系统资源控制等, 有望提升更多潜在
应用的性能. 最后, 在未来的研究中, 还需要考虑支持动态场景下的代价敏感集合成员问题, 并探索引入更多新技
术, 如机器学习等, 从而更为高效地解决此类问题.

References:
[1] Zeng ZX, Xiao RL, Lin XH, Luo TJ, Lin JY. Double locality sensitive hashing bloom filter for high-dimensional streaming anomaly