Count-min 草图
Count-min 草图是一种概率数据结构，用于估计数据流中元素的频率。
Count-min 草图
Count-Min 草图是 Redis Stack 中的一种概率数据结构，可用于估计数据流中事件/元素的频率。
它以牺牲过度计数某些事件为代价，使用亚线性空间。它消耗事件/元素流，并保留其频率的估计计数器。
非常重要的是，要知道来自 Count-Min 草图的结果低于某个阈值（由 error_rate 确定）应被忽略，甚至经常近似为零。因此，Count-Min 草图实际上是一种用于统计流中元素频率的数据结构，但它仅适用于较高的计数。非常低的计数应被忽略为噪声。
用例
产品（零售、网店）
此应用程序回答了以下问题：某产品的销售量（在某一天）是多少？
每天（期间）创建一个 Count-Min 草图。每个产品销售都会进入 CMS。CMS 为对销售贡献最大的产品提供了相当准确的结果。忽略销售总额中百分比较低的产品。
示例
假设你选择 0.1%（0.001）的错误率，确定性为 99.8%（0.998）。这意味着你的错误概率为 0.02%（0.002）。你的草图力求将错误保持在所添加所有元素总数的 0.1% 范围内。有 0.02% 的可能性，错误可能会超过此范围——就像低于阈值的元素与高于阈值的元素重叠时一样。当你向 CMS 添加一些项目并评估它们的频率时，请记住，在如此小的样本中，碰撞很少见，就像其他概率数据结构中看到的那样。
> CMS.INITBYPROB bikes:profit 0.001 0.002
OK
> CMS.INCRBY bikes:profit "Smokey Mountain Striker" 100
(integer) 100
> CMS.INCRBY bikes:profit "Rocky Mountain Racer" 200 "Cloudy City Cruiser" 150
1) (integer) 200
2) (integer) 150
> CMS.QUERY bikes:profit "Smokey Mountain Striker" "Rocky Mountain Racer" "Cloudy City Cruiser" "Terrible Bike Name"
1) (integer) 100
2) (integer) 200
3) (integer) 150
4) (integer) 0
> CMS.INFO bikes:profit
1) width
2) (integer) 2000
3) depth
4) (integer) 9
5) count
6) (integer) 450
package io.redis.examples;
public class CMSExample {
public void run() {
UnifiedJedis jedis = new UnifiedJedis("redis://localhost:6379");
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
}
}
import redis
r = redis.Redis(decode_responses=True)
res1 = r.cms().initbyprob("bikes:profit", 0.001, 0.002)
print(res1) # >>> True
res2 = r.cms().incrby("bikes:profit", ["Smoky Mountain Striker"], [100])
print(res2) # >>> [100]
res3 = r.cms().incrby(
"bikes:profit", ["Rocky Mountain Racer", "Cloudy City Cruiser"], [200, 150]
)
print(res3) # >>> [200, 150]
res4 = r.cms().query("bikes:profit", "Smoky Mountain Striker")
print(res4) # >>> [100]
res5 = r.cms().info("bikes:profit")
print(res5.width, res5.depth, res5.count) # >>> 2000 9 450
示例 1
如果我们有 1000 个元素的均匀分布，其中每个元素的计数约为 500，则阈值将为 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
此阈值似乎舒适地位于 2 个平均计数 500 和 8000 之间，因此最初选择的错误率应该适用于此情况。
调整大小
尽管 Count-Min 草图在很多方面与布隆过滤器类似，但它的调整大小要复杂得多。初始化命令仅接收两个调整大小参数，但如果你想拥有一个可用的草图，则必须彻底理解它们。
CMS.INITBYPROB key error probability
1. 误差
error 参数将确定草图的宽度 w，概率将确定哈希函数的数量（深度 d）。我们选择的错误率将确定我们可以信任草图结果的阈值。相关性是
threshold = error * total_count
或
error = threshold/total_count
其中total_count是可以通过从CMS.INFO命令的结果的count键获取的所有元素计数的总和，当然它是动态的——它会随着草图中的每次新增而改变。在创建时，你可以将total_count比率近似为草图中你期望的平均计数和元素平均数的乘积。
由于阈值是过滤器中总计数的函数，因此非常重要的是要注意，随着计数的增加，它也会增加，但是知道了总计数，我们总是可以动态计算阈值。如果结果低于它——它可以被丢弃。
2. 概率
此数据结构中的probability表示计数低于阈值的元素与所有草图/深度中计数高于阈值的元素碰撞的几率，从而返回频繁出现的元素的最小计数而不是其自身的计数。
在 CMS 中添加、更新和查询元素的时间复杂度为 O(1)。
学术来源
参考