一、预备知识
Top-k Flows：是一种用于从数据流中找出频率最高的 k 个元素的算法。这些算法通常用于处理大规模数据流，如网络流量、社交媒体数据等，以实时识别最频繁出现的元素。Top-k 流算法在许多应用场景中都非常有用，例如检测网络异常、DDoS 攻击、热门话题分析等。
Top-k 流算法包括Count-Min Sketch、Space-Saving、Filtered-Space Saving 和 HeavyKeepers各有优缺点，适用于不同的应用场景。
Count-Min(CM) Sketch：是一种概率数据结构，用于估计数据流中元素的频率。它通过多个哈希表来记录元素的出现次数，从而在有限的内存中高效地估算频率。Count-Min Sketch 可以用于 Top-k 问题，但其精度和内存使用之间需要权衡。
Conservative-Update (CU) Sketch：是一种对 Count-Min Sketch (CM Sketch) 进行优化的算法，旨在减少计数器的更新次数，从而提高估计的准确性。CU Sketch 通过保守更新策略，只在必要时更新计数器，避免了不必要的计数器值增加，从而减少了高估问题。
Counter Sum Estimation Method (CSM) Sketch：是一种用于估计数据流中元素频率的算法。它通过随机选择一个匹配的哈希桶进行插入，从而在统计阶段压缩数据，减少计数器的更新次数，提高估计的准确性。CSM Sketch 适用于需要高精度频率估计的场景，如网络流量分析和日志分析。
二、论文部分
题目：Empowering Sketches with Machine Learningfor Network Measurements
创新点：利用机器学习提升Sketch准确性的框架，大幅降低现有Sketch的错误率，为网络测量领域的研究提供了新方向。
Abstract
首先介绍了网络测量的背景和草图技术的重要性，然后提出了一个基于机器学习的框架，通过三个案例研究展示了该框架在不同网络指标测量中的应用，并通过实验结果证明了机器学习在提高草图准确性方面的有效性。
Method
图1：
机器学习框架
- 采样（Sampling）： 由于网络流量速度快，草图很快就会充满，因此需要将草图发送到远程服务器存储。文章通过采样使用一小部分数据包来生成模型，网络管理员可以根据资源情况指定采样率。
- 构建学习草图（Building learning sketch）： 使用采样数据包构建一个较小的学习草图，可以选择在交换机上构建并发送到服务器，或者直接发送数据包头到服务器构建。
- 特征提取和训练集生成（Feature extraction and Training set generation）： 从学习草图中提取特征以构建理论模型，特征的选择取决于测量的流量级指标。
- 训练（Training）： 使用学习草图和训练样本训练基于机器学习的理论模型，该模型反映了当前流量分布到感兴趣指标的映射。
- 查询（Querying）： 使用常规草图和基于机器学习的理论模型回答查询。
案例研究
- 流大小估计：识别易出错流（最小计数器值
1远小于第二小计数器值
- Top - k 流估计：针对 Top - k 流估计的估计误差和误分类误差，利用误分类流（mice flows）在最小堆中计数器很少递增的特点。分类任务用学习 CM 草图的哈希计数器值和最小堆计数器差值作特征，估计任务用学习 CM 草图哈希计数器值作特征，分别用逻辑回归和线性回归算法，查询时先识别消除误插入流 ID，再估计剩余流大小。
- 流数量估计：因 FM 草图准确估计需大值，借助机器学习，从采样集子集生成多个学习 FM 草图，用低位和高位位置作特征，目标是 FM 草图查询公式的指数部分，查询时用线性回归模型得到指数再估计流数量。
图2：
图1，图2分别为逻辑流程与实际实现
机器学习框架实现
