如何从 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

保留大小为 k 的哈希图，键是 id，值是 Item(id, count) 使用 Item 保留大小为 k 的最小堆 当事件进入时，更新 count-min 2d 数组，获取最小值，更新哈希图中的 Item，向上冒泡/向下冒泡以重新计算 Item 的顺序。如果堆大小 > k，则轮询最小项并从 hashmap 中删除 id

Answer 2

我完全同意OP的观点。在我看来，对于这个问题，Count-Min Sketch 并没有真正提供太多价值，因为它仍然会消耗相同数量的内存（尽管是哈希图解决方案使用的一半），但准确性会降低。 但看起来徐张的解决方案可行。

Answer 3

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

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

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