Count-min sketch
提示
来自deepseek解释
原文链接：https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/
Count-min sketch 命令摘要
本组共 6 条命令：
| 命令 | 摘要 | 复杂度 | 起始版本 |
|---|---|---|---|
| CMS.INCRBY | 按增量增加一个或多个元素的计数 | O(n)，其中 n 是元素数量 | 2.0.0 |
| CMS.INFO | 返回草图的信息 | O(1) | 2.0.0 |
| CMS.INITBYDIM | 按用户指定的维度初始化 Count-Min Sketch | O(1) | 2.0.0 |
| CMS.INITBYPROB | 按请求的容差初始化 Count-Min Sketch | O(1) | 2.0.0 |
| CMS.MERGE | 将多个草图合并为一个 | O(n)，其中 n 是草图数量 | 2.0.0 |
| CMS.QUERY | 返回草图中一个或多个元素的计数 | O(n)，其中 n 是元素数量 | 2.0.0 |
Count-Min Sketch 是 Redis Open Source 中的一种概率数据结构，可用于估计数据流中事件/元素的频率。
它使用亚线性空间，代价是由于哈希冲突会高估某些事件的计数。它消费事件/元素流并保持其频率的估计计数器。
非常重要的一点是，Count-Min sketch 返回的低于某个阈值（由 error_rate 决定）的结果应被忽略，甚至通常近似为零。因此，Count-Min sketch 确实是一种用于统计流中元素频率的数据结构，但仅对较高计数有用。非常低的计数应被视为噪声而忽略。
使用场景
产品（零售、在线商店）
此应用回答：某个产品（在某一天）的销量是多少？
每天（周期）创建一个 Count-Min sketch。每笔产品销售都进入 CMS。CMS 对贡献最大的产品给出相当准确的结果。占总销售额比例较低的产品被忽略。
示例
假设您选择 0.1%（0.001）的误差率，置信度为 99.8%（0.998）。这意味着您的误差概率为 0.2%（0.002）。您的草图致力于将误差控制在您已添加所有元素总数的 0.1% 以内。有 0.2% 的可能性误差会超过这个值——比如当一个低于阈值的元素与一个高于阈值的元素发生冲突时。当您向 CMS 添加少量元素并评估其频率时，请记住，在如此小的样本中，冲突很少发生，正如其他概率数据结构所见。
Count-min sketch 操作：使用 CMS.INITBYPROB 创建草图，CMS.INCRBY 递增元素计数，CMS.QUERY 估计频率，CMS.INFO 查看草图属性，用于估计数据流中的元素频率
难度： 中级
命令： CMS.INITBYPROB, CMS.INCRBY, CMS.QUERY, CMS.INFO
复杂度：
- CMS.INITBYPROB: O(1)
- CMS.INCRBY: O(n)
- CMS.QUERY: O(n)
- CMS.INFO: O(1)
Java 示例（同步 - Jedis）：
String res1 = jedis.cmsInitByProb("bikes:profit", 0.001d, 0.002d);
System.out.println(res1); // >>> OK
long res2 = jedis.cmsIncrBy("bikes:profit", "Smoky Mountain Striker", 100L);
System.out.println(res2); // >>> 100
List<Long> res3 = jedis.cmsIncrBy("bikes:profit", new HashMap<String, Long>() {{
put("Rocky Mountain Racer", 200L);
put("Cloudy City Cruiser", 150L);
}});
System.out.println(res3); // >>> [200, 150]
List<Long> res4 = jedis.cmsQuery("bikes:profit", "Smoky Mountain Striker");
System.out.println(res4); // >>> [100]
Map<String, Object> res5 = jedis.cmsInfo("bikes:profit");
System.out.println(res5.get("width") + " " + res5.get("depth") + " " + res5.get("count")); // >>> 2000 9 450示例 1：
如果我们有 1000 个元素的均匀分布，每个元素的计数大约为 500，则阈值为：
threshold = error * total_count = 0.001 * (1000*500) = 500这表明 CMS 可能不是统计均匀分布流频率的最佳数据结构。让我们尝试将误差降低到 0.01%：
threshold = error * total_count = 0.0001 * (1000*500) = 100这个阈值看起来已经更可接受，但这意味着我们需要更大的草图宽度 w = 2/error = 20 000，因此需要更多内存。
示例 2：
在另一个示例中，想象一个正态（高斯）分布，我们有 1000 个元素，其中 800 个的总计数为 400K（平均计数 500），200 个元素的总计数要高得多，为 1.6M（平均计数 8000），使它们成为重击者（大象流）。在将所有 1000 个元素“填充”到草图后，阈值为：
threshold = error * total_count = 0.001 * 2M = 2000这个阈值似乎恰好在两个平均计数 500 和 8000 之间，因此初始选择的误差率在这种情况下应该工作良好。
大小设定
尽管 Count-Min sketch 在许多方面与布隆过滤器相似，但其大小设定要复杂得多。初始化命令只接收两个大小参数，但如果您想拥有一个可用的草图，必须彻底理解它们。
CMS.INITBYPROB key error probability1. 误差
error 参数将确定草图的宽度 w，概率将确定哈希函数的数量（深度 d）。我们选择的误差率将决定我们可以信任草图结果的阈值。相关性为：
threshold = error * total_count或
error = threshold/total_count其中 total_count 是所有元素计数的总和，可以从 CMS.INFO 命令结果的 count 键中获得，并且当然是动态的——它会随着草图中的每次新递增而变化。在创建时，您可以近似 total_count 比率，作为草图中预期的平均计数与平均元素数量的乘积。
由于阈值是过滤器中总计数的一个函数，注意它会随着计数的增长而增长，但知道总计数后，我们可以随时动态计算阈值。如果结果低于它，则可以丢弃。
2. 概率
probability 在此数据结构中表示计数低于阈值的元素与计数高于阈值的元素在所有草图/深度上发生冲突的概率，从而返回频繁出现元素的最小计数而不是其自身。
性能
在 CMS 中添加、更新和查询元素的平均时间复杂度为 O(1)。