Top-K
Top-K 是一种概率数据结构，可让您在数据流中找到最常见的项目。
Top K 是 Redis Stack 中的一种概率数据结构，用于估计K流中排名最高的元素。
在这种情况下，“最高排名”是指“附加了最高数字或分数的元素”，其中分数可以是元素在流中出现的次数的计数 - 因此，数据结构非常适合查找流中频率最高的元素。 一个非常常见的应用是检测网络异常和 DDoS 攻击，Top K 可以回答以下问题：发送到同一地址或同一 IP 的请求流量是否突然增加？
确实，与 Count-Min Sketch 的功能有一些重叠，但这两种数据结构有其差异，应应用于不同的用例。
Top-K 的 Redis Stack 实现基于 Junzhi Gong 等人提出的 HeavyKeepers 算法。它摒弃了一些较旧的方法，如 “count-all” 和 “admit-all count-some”，转而采用 “count-with-exponential-decay” 策略，该策略偏向于小鼠（小）流，对大象（大）流的影响有限。此实现同时使用两种数据结构：一个包含概率计数的哈希表（很像 Count-Min Sketch），以及一个包含该K计数最高的项。这确保了高准确性和比以前的概率算法更短的执行时间，同时将内存利用率保持在 Sorted Set 通常所需的一小部分。它还有一个额外的好处，即能够在 Top K 列表中添加或删除元素时获得实时通知。
用例
热门话题标签（社交媒体平台、新闻发布网络）
此应用程序回答了以下问题：
- 在过去 X 小时内人们提到最多的 K 主题标签是什么？
- 今天阅读/观看次数最高的 K news 是什么？
数据流是传入的社交媒体帖子，您可以从中解析出不同的主题标签。
这TOPK.LISTcommand 的时间复杂度为O(K*log(k))所以如果K较小，则无需保留所有主题标签的单独集合或排序集合。您可以直接从 Top K 本身进行查询。
例
此示例将向您展示如何跟踪在线购物时使用的关键字 “bike”;例如，“Bike Store” 和 “Bike Handlebars”。按如下方式作。
- 用
TOPK.RESERVE以使用特定参数初始化前 K 个草图。注意：width,depth和decay_constant参数可以省略，因为它们将分别设置为默认值 7、8 和 0.9（如果不存在）。
> TOPK.RESERVE key k width depth decay_constant
-
用
TOPK.ADD将项目添加到草图中。如您所见，可以同时添加多个项目。如果在添加其他项目时返回一个项目，则意味着该项目已从前 5 个项目的最小堆中降级，低于该项则意味着返回的项目不再在前 5 个项目中，否则nil返回。这允许对进入或驱逐前 K 列表中的项目进行动态重量级检测。 在下面的示例中，“pedals” 取代了 “handlebars”，后者在添加 “pedals” 后返回。另请注意，第二次添加 “store” 和 “seat” 不会返回任何内容，因为它们已经在前 K 中。 -
用
TOPK.LIST列出到目前为止输入的项目。 -
用
TOPK.QUERY以查看项目是否在前 K 列表中。就像TOPK.ADD可以同时查询多个项。
Sizing
Choosing the size for a Top K sketch is relatively easy, because the only two parameters you need to set are a direct function of the number of elements (K) you want to keep in your list.
If you start by knowing your desired k you can easily derive the width and depth:
width = k*log(k)
depth = log(k) # but a minimum of 5
For the decay_constant you can use the value 0.9 which has been found as optimal in many cases, but you can experiment with different values and find what works best for your use case.
Performance
Insertion in a top-k has time complexity of O(K + depth) ≈ O(K) and lookup has time complexity of O(K), where K is the number of top elements to be kept in the list and depth is the number of hash functions used.
Academic sources
References
On this page