Ark Filter: A General and Space-Efficient Sketch for Network Flow Analysis
Ark Filter: A General and Space-Efficient Sketch for Network Flow Analysis
复制标题
DOI：
10.1109/tnet.2023.3263839
复制
发表时间：
2023-12
期刊：
影响因子：
--
通讯作者：
Lailong Luo;Pengtao Fu;Shangsen Li;Deke Guo;Qianzhen Zhang;Huaimin Wang
中科院分区：
文献类型：
--
作者：
Lailong Luo;Pengtao Fu;Shangsen Li;Deke Guo;Qianzhen Zhang;Huaimin Wang
草图被广泛部署来表示网络流以支持复杂的流分析。典型的草图通常使用哈希函数将元素映射到哈希表或位数组中。此类草图在吞吐量、灵活性和功能方面仍然存在潜在的弱点。为此，我们提出了 Ark 过滤器，这是一种新颖的草图，它使用两个候选存储桶中的任何一个来存储元素信息，该两个候选存储桶由指纹和过滤器长度之间的商或余数索引。这样，以后的查询或重新分配就不需要进一步的哈希计算。我们进一步扩展了 Ark 过滤器，以实现容量弹性和更多功能（例如频率估计和 top-$k$ 查询）。综合实验表明，与Cuckoo Filter相比，Ark Filter的删除、插入、混合查询吞吐量分别为$2.08\times $、$1.34\times $、$1.68\times $；与 Quotient 过滤器相比，方舟过滤器的删除、插入、混合查询吞吐量分别为 $4.55\times $ 、 $1.74\times $ 和 $22.12\times $ ；与布隆过滤器相比，方舟过滤器的插入和混合查询吞吐量分别为 $2.55\times $ 和 $2.11\times $。
Sketches are widely deployed to represent network flows to support complex flow analysis. Typical sketches usually employ hash functions to map elements into a hash table or bit array. Such sketches still suffer from potential weaknesses upon throughput, flexibility, and functionality. To this end, we propose Ark filter, a novel sketch that stores the element information with either of two candidate buckets indexed by the quotient or remainder between the fingerprint and filter length. In this way, no further hash calculations are required for future queries or reallocations. We further extend the Ark filter to enable capacity elasticity and more functionalities (such as frequency estimation and top- $k$ query). Comprehensive experiments demonstrate that, compared with Cuckoo filter, Ark filter has $2.08\times $ , $1.34\times $ , and $1.68\times $ throughput of deletion, insertion, and hybrid query, respectively; compared with Quotient filter, Ark filter has $4.55\times $ , $1.74\times $ , and $22.12\times $ throughput of deletion, insertion, and hybrid query, respectively; compared with Bloom filter, Ark filter has $2.55\times $ and $2.11\times $ throughput of insertion and hybrid query, respectively.