PeakSketch:检测网络流中的top-k流的无偏和通用草图  

PeakSketch:Unbiased and Generalized Sketch for Detecting top-k Flows in Network Streams

作　　者：李旭 王超[1] 尹慰民 周萍 LI Xu;WANG Chao;YIN Weimin;ZHOU Ping(School of Electrical Engineering,University of South China,Hengyang,Hunan 421001,China)

机构地区：[1]南华大学电气工程学院,湖南衡阳421001

出　　处：《南华大学学报（自然科学版）》2024年第2期73-81,共9页Journal of University of South China：Science and Technology

摘　　要：通过对现有Sketch结构的研究,提出一种新的Sketch结构:PeakSketch,本文将其应用于三种任务:检测top-k频繁流,检测top-k重变化流,检测top-k持久流,从理论上证明了PeakSketch可以提供无偏估计,并且给出了算法的误差界。实验结果表明,PeakSketch的各项性能优秀,在检测top-k频繁流任务中,PeakSketch的吞吐量显著提升,特别是在分配内存小于200 kB以下时,吞吐量最高提升可以达到50%,准确率最高提升一倍,PeakSketch也展现突出的性能。By studying existing sketch structures,this paper proposes a new sketch structure called PeakSketch,which is applied to three tasks:detecting top-k frequent flows,detecting top-k heavy change flows,and detecting top-k persistent flows.Theoreti-cally,it is proven that PeakSketch can provide unbiased estimates,and the algorithms er-ror is analyzed.Experimental results demonstrate that PeakSketch excels in various per-formance metrics.In the task of detecting top-k frequent flows,PeakSketchs throughput is significantly enhanced,especially when the allocated memory is less than 200 kB,with throughput improvements of up to 50%and precision improvements of up to double.Peak-Sketch showcases outstanding performance.

关 键 词：网络流测量 SKETCH 无偏估计 top-k流检测 频繁流 重变化流 持久流 

分 类 号：TP393.06[自动化与计算机技术—计算机应用技术]