计数最小化草图
计数最小化草图是一种概率性数据结构，用于估计数据流中元素的频率。
计数最小化草图是 Redis Stack 中的一种概率性数据结构，可用于估计数据流中事件/元素的频率。
它以牺牲由于冲突导致某些事件被过度计数为代价，使用次线性空间。它使用事件/元素流，并保持其频率的估计计数器。
了解 Count-Min Sketch 的结果非常重要，低于某个阈值（由 error_rate 决定）的结果应该被忽略，甚至经常被近似为零。因此，Count-Min Sketch 实际上是一种用于计数流中元素频率的数据结构，但它只对较高计数有效。非常低的计数应该被忽略，视为噪声。
用例
产品（零售、在线商店）
此应用程序回答了这个问题：某产品的销量（在特定日期）是多少？
使用每天（周期）创建一个 Count-Min Sketch。每个产品的销量都会进入 CMS。CMS 会对对销量贡献最大的产品提供相当准确的结果。销售额占比低的商品会被忽略。
示例
假设您选择了一个 0.1%（0.001）的误差率，确定性为 99.8%（0.998）。这意味着您的错误概率为 0.02%（0.002）。您的 Sketch 努力将误差控制在您添加的所有元素的总计数的 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
"""
Code samples for Count-min sketch doc pages:
https://redis.ac.cn/docs/latest/develop/data-types/probabilistic/count-min-sketch/
"""
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
import assert from 'assert';
import { createClient } from 'redis';
const client = createClient();
await client.connect();
const res1 = await client.cms.initByProb('bikes:profit', 0.001, 0.002);
console.log(res1); // >>> OK
const res2 = await client.cms.incrBy('bikes:profit', {
item: 'Smoky Mountain Striker',
incrementBy: 100
});
console.log(res2); // >>> [100]
const res3 = await client.cms.incrBy('bikes:profit', [
{
item: 'Rocky Mountain Racer',
incrementBy: 200
},
{
item: 'Cloudy City Cruiser',
incrementBy: 150
}
]);
console.log(res3); // >>> [200, 150]
const res4 = await client.cms.query('bikes:profit', 'Smoky Mountain Striker');
console.log(res4); // >>> [100]
const res5 = await client.cms.info('bikes:profit');
console.log(res5.width, res5.depth, res5.count); // >>> 2000 9 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
}
}
using NRedisStack.CountMinSketch.DataTypes;
using NRedisStack.RedisStackCommands;
using NRedisStack.Tests;
using StackExchange.Redis;
public class Cms_tutorial
{
[SkipIfRedis(Is.OSSCluster)]
public void run()
{
var muxer = ConnectionMultiplexer.Connect("localhost:6379");
var db = muxer.GetDatabase();
bool res1 = db.CMS().InitByProb("bikes:profit", 0.001, 0.002);
Console.WriteLine(res1); // >>> True
long res2 = db.CMS().IncrBy("bikes:profit", "Smoky Mountain Striker", 100);
Console.WriteLine(res2); // >>> 100
long[] res3 = db.CMS().IncrBy("bikes:profit",
new Tuple<RedisValue, long>[]{
new Tuple<RedisValue, long>("Rocky Mountain Racer", 200),
new Tuple<RedisValue, long>("Cloudy City Cruiser", 150)
}
);
Console.WriteLine(string.Join(", ", res3)); // >>> 200, 150
long[] res4 = db.CMS().Query("bikes:profit", new RedisValue[] { "Smoky Mountain Striker" });
Console.WriteLine(string.Join(", ", res4)); // >>> 100
CmsInformation res5 = db.CMS().Info("bikes:profit");
Console.WriteLine($"Width: {res5.Width}, Depth: {res5.Depth}, Count: {res5.Count}");
// >>> Width: 2000, Depth: 9, Count: 450
// Tests for 'cms' step.
}
}
示例 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
这个阈值看起来已经更可接受了，但这意味着我们需要更大的 Sketch 宽度 w = 2/error = 20 000，因此需要更多内存。
示例 2
在另一个示例中，让我们想象一个正态（高斯）分布，其中我们有 1000 个元素，其中 800 个元素的总计数为 400K（平均计数为 500），而 200 个元素的总计数为 1.6M（平均计数为 8000），使它们成为重击者（大象流）。在用所有 1000 个元素“填充” Sketch 之后，阈值为
threshold = error * total_count = 0.001 * 2M = 2000
这个阈值似乎舒适地位于 2 个平均计数 500 和 8000 之间，因此最初选择的误差率应该适用于这种情况。
大小
尽管 Count-Min Sketch 在许多方面与 Bloom 过滤器相似，但它的尺寸要复杂得多。初始化命令只接收两个尺寸参数，但如果您想拥有可用的 Sketch，则必须彻底了解它们。
CMS.INITBYPROB key error probability
1. 误差
error 参数将确定 Sketch 的宽度 w，概率将确定哈希函数的数量（深度 d）。我们选择的误差率将决定我们能够信任 Sketch 中结果的阈值。相关性是
threshold = error * total_count
或
error = threshold/total_count
其中 total_count 是可以从 CMS.INFO 命令结果的 count 键获得的所有元素的计数总和，并且是动态的 - 它会随着 Sketch 中的每次新的增量而改变。在创建时，您可以将 total_count 比例近似为 Sketch 中您预期得到的平均计数和平均元素数量的乘积。
由于阈值是过滤器中总计数的函数，因此需要注意的是，它会随着计数的增长而增长，但知道总计数，我们始终可以动态计算阈值。如果结果低于它 - 它可以被丢弃。
2. 概率
此数据结构中的 probability 表示在所有 Sketch/深度上与计数高于阈值的元素发生碰撞的计数低于阈值的元素的机会，因此返回频繁出现的元素的最小计数而不是它自己的计数。
在 CMS 中添加、更新和查询元素的时间复杂度为 O(1)。
学术来源
参考文献