Count-min 草图

Count-min sketch 是一种概率数据结构，用于估计数据流中元素的频率。

Count-Min Sketch 是 Redis Stack 中的一种概率数据结构，可用于估计数据流中事件/元素的频率。

它使用亚线性空间，代价是由于冲突而过度计数一些事件。它消耗事件/元素的流，并保持其频率的估计计数器。

了解来自Count-Min草图的结果低于某个阈值（由error_rate确定）时应被忽略，并且通常甚至近似为零，这一点非常重要。因此，Count-Min草图确实是一种用于计算流中元素频率的数据结构，但它仅对较高的计数有用。非常低的计数应被视为噪声而忽略。

使用案例

产品（零售、在线商店）

这个应用程序回答了这个问题：某一天某个产品的销售量是多少？

每天（周期）使用一个Count-Min sketch。每个产品销售都进入CMS。CMS为对销售贡献最大的产品提供相当准确的结果。占总销售额比例较低的产品被忽略。

示例

假设您选择了一个错误率为0.1%（0.001）且确定性为99.8%（0.998）。这意味着您的错误概率为0.02%（0.002）。您的草图努力将错误保持在您添加的所有元素总数的0.1%以内。有0.02%的可能性错误可能会超过这个范围——例如，当一个低于阈值的元素与一个高于阈值的元素重叠时。当您向CMS添加一些项目并评估它们的频率时，请记住，在如此小的样本中，碰撞是罕见的，正如其他概率数据结构中所见。

>_ Redis CLI

> 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

Python

"""
Code samples for Count-min sketch doc pages:
    https://redis.io/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

Node.js

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

Java-Sync

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
  }

}

package example_commands_test

import (
	"context"
	"fmt"

	"github.com/redis/go-redis/v9"
)


func ExampleClient_cms() {
	ctx := context.Background()

	rdb := redis.NewClient(&redis.Options{
		Addr:     "localhost:6379",
		Password: "", // no password docs
		DB:       0,  // use default DB
	})


	res1, err := rdb.CMSInitByProb(ctx, "bikes:profit", 0.001, 0.002).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res1) // >>> OK

	res2, err := rdb.CMSIncrBy(ctx, "bikes:profit",
		"Smoky Mountain Striker", 100,
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res2) // >>> [100]

	res3, err := rdb.CMSIncrBy(ctx, "bikes:profit",
		"Rocky Mountain Racer", 200,
		"Cloudy City Cruiser", 150,
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res3) // >>> [200 150]

	res4, err := rdb.CMSQuery(ctx, "bikes:profit",
		"Smoky Mountain Striker",
	).Result()

	if err != nil {
		panic(err)
	}

	fmt.Println(res4) // >>> [100]

	res5, err := rdb.CMSInfo(ctx, "bikes:profit").Result()

	if err != nil {
		panic(err)
	}

	fmt.Printf("Width: %v, Depth: %v, Count: %v",
		res5.Width, res5.Depth, res5.Count)
	// >>> Width: 2000, Depth: 9, Count: 450

}


using NRedisStack.CountMinSketch.DataTypes;
using NRedisStack.RedisStackCommands;
using NRedisStack.Tests;
using StackExchange.Redis;



public class Cms_tutorial
{

    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

这个阈值看起来已经更可接受了，但这意味着我们需要一个更大的草图宽度 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草图在许多方面与布隆过滤器相似，但其大小调整要复杂得多。初始化命令仅接收两个大小参数，但如果你想拥有一个可用的草图，你必须彻底理解它们。

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)。

学术资源

改进的数据流摘要：Count-Min Sketch及其应用

参考文献

Count-Min Sketch: 估计事物的艺术与科学