Top-K
提示
来自deepseek解释
原文链接：https://redis.io/docs/latest/develop/data-types/probabilistic/top-k/
Top-K 命令摘要
本组共 7 条命令：
| 命令 | 摘要 | 复杂度 | 起始版本 |
|---|---|---|---|
| TOPK.ADD | 向 Top-K 草图中添加一个元素。可同时添加多个元素。 | O(n * k)，其中 n 是元素数量，k 是 Top-K 值... | 2.0.0 |
| TOPK.COUNT | 返回草图中一个或多个元素的计数 | O(n)，其中 n 是元素数量 | 2.0.0 |
| TOPK.INCRBY | 按增量增加一个或多个元素的计数 | O(n * k * incr)，其中 n 是元素数量... | 2.0.0 |
| TOPK.INFO | 返回草图的信息 | O(1) | 2.0.0 |
| TOPK.LIST | 返回 Top-K 草图中的完整元素列表。 | O(k*log(k))，其中 k 是 Top-K 值 | 2.0.0 |
| TOPK.QUERY | 检查一个或多个元素是否在草图中 | O(n)，其中 n 是元素数量 | 2.0.0 |
| TOPK.RESERVE | 使用指定参数初始化 Top-K 草图 | O(1) | 2.0.0 |
Top-K 是 Redis Open Source 中的一种概率数据结构，用于估计数据流中排名最高的 K 个元素。
这里的“排名最高”指的是“具有最高数量或分数的元素”，其中分数可以是元素在流中出现的次数——因此该数据结构非常适合查找流中出现频率最高的元素。一个非常常见的应用是检测网络异常和 DDoS 攻击，Top-K 可以回答：对同一地址或来自同一 IP 的请求流量是否突然增加？
确实，Top-K 与 Count-Min Sketch 的功能有一定重叠，但这两种数据结构各有不同，应适用于不同的使用场景。
Redis Open Source 对 Top-K 的实现基于 Junzhi Gong 等人提出的 HeavyKeepers 算法。它摒弃了“全计数”和“全准入-部分计数”等较旧的方法，采用“指数衰减计数”策略，该策略对鼠标流（小流量）有偏差，对大象流（大流量）影响有限。该实现同时使用两种数据结构：一个保存概率计数的哈希表（很像 Count-Min Sketch）和一个保存计数最高的 K 个元素的最小堆。这确保了高精度和比以往概率算法更短的执行时间，同时将内存利用率保持在排序集合通常所需的一小部分。它的额外好处是能够在元素被添加或从 Top-K 列表中移除时获得实时通知。
使用场景
热门话题标签（社交媒体平台、新闻分发网络）
此应用回答以下问题：
- 在过去 X 小时内，人们提及最多的 K 个话题标签是什么？
- 今天阅读/观看次数最高的 K 条新闻是什么？
数据流是传入的社交媒体帖子，您从中解析出不同的话题标签。
TOPK.LIST 命令的时间复杂度为 O(K*log(k))，因此如果 K 很小，则无需为所有话题标签维护单独的集合或排序集合。您可以直接从 Top-K 本身查询。
示例
此示例将向您展示如何跟踪在线购物时使用的“bike”相关关键词，例如“bike store”和“bike handlebars”。操作如下。
- 使用
TOPK.RESERVE使用特定参数初始化 Top-K 草图。注意：width、depth和decay_constant参数可以省略，如果不存在则分别设置为默认值 7、8 和 0.9。
> TOPK.RESERVE key k width depth decay_constant- 使用
TOPK.ADD向草图中添加元素。如您所见，可以同时添加多个元素。如果在添加其他元素时返回某个元素，表示该元素已从顶部元素的最小堆中被淘汰，即返回的元素不再位于前 5 名中，否则返回nil。这允许对进入或退出 Top-K 列表的元素进行动态重击者检测。
在下面的示例中，“pedals”取代了“handlebars”，在添加“pedals”后返回“handlebars”。另请注意，“store”和“seat”的第二次添加没有返回任何内容，因为它们已经在 Top-K 中。
使用
TOPK.LIST列出迄今为止输入的元素。使用
TOPK.QUERY查看某个元素是否在 Top-K 列表中。与TOPK.ADD一样，可以同时查询多个元素。
Top-K 操作：使用 TOPK.RESERVE 初始化草图，TOPK.ADD 跟踪元素频率，TOPK.LIST 获取顶部元素，TOPK.QUERY 检查成员资格，用于识别数据流中最频繁的元素
难度： 中级
命令： TOPK.RESERVE, TOPK.ADD, TOPK.LIST, TOPK.QUERY
复杂度：
- TOPK.RESERVE: O(1)
- TOPK.ADD: O(n * k)
- TOPK.LIST: O(k*log(k))
- TOPK.QUERY: O(n)
Java 示例（同步 - Jedis）：
String res1 = jedis.topkReserve("bikes:keywords", 5L, 2000L, 7L, 0.925D);
System.out.println(res1); // >>> True
List<String> res2 = jedis.topkAdd("bikes:keywords",
"store",
"seat",
"handlebars",
"handles",
"pedals",
"tires",
"store",
"seat");
System.out.println(res2); // >>> [None, None, None, None, None, 'handlebars', None, None]
List<String> res3 = jedis.topkList("bikes:keywords");
System.out.println(res3); // >>> ['store', 'seat', 'pedals', 'tires', 'handles']
List<Boolean> res4 = jedis.topkQuery("bikes:keywords", "store", "handlebars");
System.out.println(res4); // >>> [1, 0]大小设定
为 Top-K 草图选择大小相对容易，因为您只需要设置的两个参数直接与您希望在列表中保留的元素数量（K）相关。
如果您从已知的期望 k 开始，可以轻松推导出宽度和深度：
width = k*log(k)
depth = log(k) # 但最小为 5对于 decay_constant，您可以使用 0.9 值，该值在许多情况下被证明是最优的，但您可以尝试不同的值，找到最适合您使用场景的值。
性能
Top-K 中的插入时间复杂度为 O(K + depth) ≈ O(K)，查找时间复杂度为 O(K)，其中 K 是要保留在列表中的顶部元素数量，depth 是使用的哈希函数数量。