基于滑动时间窗口模型的流基数估计算法

Per-flow cardinality estimation algorithm under sliding window model

基于滑动时间窗口模型的流基数估计是指在某一时刻对过去一个时间窗口内每条流的基数进行估计。相较于传统的离散时间窗口模型,基于滑动时间窗口模型的流基数估计具有实时性更高、片上存储空间开销更小的优势。现有研究需要为每条流分配独立的存储空间,这在紧缺的片上高速存储资源条件下是无法实现的。针对上述问题,文章提出了一种新的基于滑动时间窗口模型的流基数估计(Sliding virtual Hyperloglog,SvHLL)算法,在片上引入虚拟寄存器技术保存多条流的流信息。该算法采用对一条流的两部分虚拟寄存器分别进行基数估计并相减的方式去除噪声,不再需要扫描整个物理寄存器组,提高了基数估计的效率。仿真实验结果表明,SvHLL算法在2MB和4MB的片上存储空间下以及在10s,20s和60s的滑动时间窗口下的平均相对误差与平均绝对误差均在11以下,基数估计性能较好。

Per-flow cardinality estimation under sliding window model is to estimate at any time cardinality of every flow over the duration bounded by the length of the sliding window.Compared to discrete window model,cardinality estimation under sliding window model has the advantage of higher real-time performance and lower overhead of on-chip memory.Previous researches allocate independent memory for a single flow which is infeasible under strictly limited on-chip high-speed memory resources.This paper proposes a new per-flow cardinality estimation algorithm under sliding window model.The proposed algorithm introduces virtual register technique to store all flows'information.The algorithm removes noise by estimating and subtracting the cardinality of two half of virtual registers of a flow,eliminating the need to scan the entire physical register array,thereby improving the efficiency of cardinality estimation.The simulation results show that the average relative error and average absolute error of the SvHLL algorithm are all below 11 under 2 MB and 4 MB on-chip storage space and the sliding windows of 10 s,20 s and 60 s.Hence,the proposed algorithm has good performance on per-flow cardinality estimation.