我正在阅读如何使用概率数据结构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, ...]
. 如果我们使用相同的逻辑来更新我们的最小堆,我们会得到不正确的答案(有重复)。
我肯定在这里遗漏了一些东西。请帮我理解。