李旭,王超,尹慰民,周萍.PeakSketch:检测网络流中的top-k流的无偏和通用草图[J].南华大学学报(自然科学版),2024,(2):73~81.[LI Xu,WANG Chao,YIN Weimin,ZHOU Ping.PeakSketch:Unbiased and Generalized Sketch for Detecting top-k Flows in Network Streams[J].Journal of University of South China(Science and Technology),2024,(2):73~81.] |
PeakSketch:检测网络流中的top-k流的无偏和通用草图 |
PeakSketch:Unbiased and Generalized Sketch for Detecting top-k Flows in Network Streams |
投稿时间:2023-12-23 |
DOI:10.19431/j.cnki. 1673-0062.2024.02.010 |
中文关键词: 网络流测量 Sketch 无偏估计 top-k流检测 频繁流 重变化流 持久流 |
英文关键词:network flow measurement Sketch unbiased estimation detecting top-k flows frequent flows heavy change flows persistent flows |
基金项目: |
|
摘要点击次数: 0 |
全文下载次数: 0 |
中文摘要: |
通过对现有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. Theoretically, it is proven that PeakSketch can provide unbiased estimates, and the algorithm's error is analyzed. Experimental results demonstrate that PeakSketch excels in various performance metrics. In the task of detecting top-k frequent flows, PeakSketch's 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. PeakSketch showcases outstanding performance. |
查看全文 查看/发表评论 下载PDF阅读器 |
关闭 |
|
|
|