如何从 count-min-sketch 中获取前 K 个元素？

Question

我正在阅读如何使用概率数据结构count-min-sketch来查找数据流中的前 k 个元素。但我似乎无法理解我们维护堆以获得最终答案的步骤。

问题：

我们有一个项目流[B, C, A, B, C, A, C, A, A, ...]。我们被要求找出前 k 个最常出现的项目。

我的理解是，这可以使用微批处理来完成，在微批处理中，我们在开始做一些实际工作之前积累 N 个项目。

hashmap +heap方法对我来说很容易理解。我们遍历微批次并{B:34, D: 65, C: 9, A:84, ...}通过计算元素来构建频率图（例如 ）。然后，我们通过遍历频率图来维护大小为 k 的最小堆，根据[item]:[freq]需要向堆添加和从堆中删除。足够简单，没有什么花哨的。

现在使用CMS+heap，而不是哈希图，我们有了这个概率有损二维数组，我们通过遍历微批次来构建它。问题是：给定这个 CMS，我们如何维护大小为 k 的最小堆？

CMS只包含一堆数字，而不是原始项目。除非我还保留微批次中的一组独特元素，否则我无法知道最后需要针对哪些项目构建堆。但如果我这样做，那不是违背了使用CMS节省内存空间的目的吗？

我还考虑过在遍历列表时实时构建堆。随着每个项目的进入，我们可以快速更新 CMS 并获取该项目在该点的累积频率。但这个频率数字是累积的这一事实对我没有多大帮助。例如，通过上面的示例流，我们将得到[B:1, C:1, A:1, B:2, C:2, A:2, C:3, A:3, A:4, ...]. 如果我们使用相同的逻辑来更新我们的最小堆，我们将得到不正确的答案（有重复）。

我肯定在这里遗漏了一些东西。请帮助我理解。

Answer 1

以下解释来自此YouTube 视频的评论：

我们需要存储密钥，但只有 K 个（或更多）。不是全部。当每把钥匙到来时，我们都会执行以下操作：

• 将其添加到计数分钟草图中。
• 从计数分钟草图中获取按键计数。
• 检查当前键是否在堆中。如果它出现在堆中，我们就在那里更新它的计数值。如果堆中不存在，我们检查堆是否已满。如果未满，我们将此键添加到堆中。如果堆已满，我们检查最小堆元素并将其值与当前键计数值进行比较。此时，我们可以删除最小元素并添加当前键（如果当前键计数>最小元素值）。