algorithm - Count-Min Sketch 和Heavy-Hitters 问题

Question

我正在阅读 Count-Min Sketch 数据结构，它根据错误概率参数和容差参数为点和范围查询提供概率答案。例如，CM 可以回答“项目 x 以 10% 的概率出现在数据流中的次数”这个问题。

重击者的相关问题也出现了。在为 HH 问题实现最小堆时，我注意到各种研究论文指出，只有当草图中项目的最小计数大于阈值时，我们才插入堆中。

我的问题是，这是否意味着我们正在概率性地回答重击手问题？相应的问题会是“有 10% 的概率，哪个项目是数据流中第二频繁的？”

标签： algorithmdata-structurescount-min-sketch

Answer 1

来自维基百科：

在数据流模型中，频繁元素问题是输出一组元素，这些元素构成了流的某个固定部分以上。一种特殊情况是多数问题，即确定任何值是否构成流的多数。

更正式地说，固定某个正常数 c > 1，令流的长度为 m，令 fi 表示值 i 在流中出现的频率。频繁元素问题是输出集合 { i | f > m/c }。

一些值得注意的算法是：

• Boyer-Moore 多数投票算法
• Karp-Papadimitriou-Shenker 算法
• Count-Min 草图
• 粘性抽样
• 有损计数
• 采样和保持
• 多级布隆过滤器
• 计数草图
• 草图引导采样

事件检测 检测数据流中的事件通常使用上面列出的重击算法：使用这些算法之一确定最频繁的项目及其频率，然后将前一个时间点的最大增加报告为趋势。这种方法可以通过使用指数加权移动平均值和方差进行标准化来改进。

所以，是的。CMS 可用于确定频率（以近似方式），可用于回答 HH 问题。