4

我正在阅读如何使用概率数据结构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，而不是 hashmap，我们有了这个概率有损 2D 数组，我们通过遍历 micro-batch 来构建它。问题是：给定这个 CMS，我们如何维护大小为 k 的最小堆？

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

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

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

4

1 回答 1

0

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

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

  • 将其添加到 count-min 草图。
  • 从 count-min 草图中获取键数。
  • 检查当前键是否在堆中。如果它出现在堆中，我们会在那里更新它的计数值。如果它不在堆中，我们检查堆是否已经满。如果未满，我们将此键添加到堆中。如果堆已满，我们检查最小堆元素并将其值与当前键计数值进行比较。此时我们可以删除最小元素并添加当前键（如果当前键计数>最小元素值）。
于 2021-06-13T16:34:19.293 回答