| 摘要: |
| 布谷鸟过滤器是一种空间高效的近似成员资格查询数据结构, 在网络系统中被广泛应用于网络路由、网络测量和网络缓存等. 然而, 传统的布谷鸟过滤器设计并未充分考虑在网络系统中, 部分或全部查询集合已知的情况, 以及这部分查询具有代价的情况. 这导致现有的布谷鸟过滤器在该情况下性能无法达到最优. 为此, 设计了指纹可变哈希布谷鸟过滤器(VHCF). VHCF提出了指纹可变哈希技术, 感知已知的查询集合及其代价, 通过为每个哈希桶搜索最优指纹哈希函数, 从而大幅降低误判代价. 随后, 每个哈希桶的最优指纹哈希函数会被独立地记录进入每个哈希桶内的哈希索引单元. 此外, 提出了一种单哈希的技术用于降低引入指纹可变哈希技术导致的额外计算开销, 还对VHCF的操作复杂度和误判率进行了理论分析. 最后, 实验和理论结果都一致表明, VHCF在保证查询吞吐量相当的情况下, 取得了比现有布谷鸟过滤器及其变种都要低的误判率. 特别的, 在保持指纹长度相同的情况下, VHCF只需为每个哈希索引单元分配 1–2比特, 即可相比标准布谷鸟过滤器降低误判率12.5%–50%. |
| 关键词: 布谷鸟过滤器 代价敏感 集合成员查询 误判率 |
| DOI：10.13328/j.cnki.jos.007221 |
| 分类号:TP393 |
| 基金项目: |
|
| Cost-sensitive Variable Hashing-fingerprint Cuckoo Filter |
|
LI Meng, LUO Wen-Qi, DAI Hai-Peng, WANG Han-Cheng, GU Rong, CHEN Gui-Hai
|
|
School of Computer Science, Nanjing University, Nanjing 210023, China
|
| Abstract: |
| A cuckoo filter is a space-efficient approximate membership query data structure, widely used in network systems for applications such as network routing, network measurement, and network caching. However, the traditional design of cuckoo filters has not adequately considered the scenario in network systems where some or all queries in the collection are known, and these queries come with associated costs. This limitation results in the suboptimal performance of existing cuckoo filters in such situations. To address this, the variable hashing-fingerprint cuckoo filter (VHCF) has been developed. VHCF introduces variable fingerprint hashing technology, taking into account the known query collection and their associated costs. By searching for the optimal fingerprint hash function for each hash bucket, the overall cost of false positives is significantly reduced. In addition, this study proposes a single-hash technology to reduce the additional computational overhead caused by the variable-hash technology. A theoretical analysis of the operational complexity and false positive rate of VHCF is also provided. Finally, experimental and theoretical results both demonstrate that VHCF achieves a significantly lower false positive rate than existing cuckoo filters and their variants while ensuring comparable query throughput. Specifically, VHCF only needs to allocate 1–2 bits for each hash index unit, which can reduce the false positive rate to 12.5%–50% of the original. |
| Key words: cuckoo filter cost-sensitivity membership testing false positive rate |
