问题标签 [count-min-sketch]

我正在阅读如何使用概率数据结构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, ...]. 如果我们使用相同的逻辑来更新我们的最小堆，我们会得到不正确的答案（有重复）。

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

count-min 草图是一种概率数据结构，用于在多集中有损存储计数。它接收更新(i, c)wherei是集合的一个元素并且是该元素的c非负数，然后使用散列函数做一些聪明的事情。它在 SO 和其他地方被广泛讨论；这是原始论文 ( PDF ) 和Wikipedia 文章。基于我正在考虑的应用程序——来自单细胞基因组学实验的计数数据的有损存储——让我们假设i和c都是整数。这对i,c意味着在给定的生物细胞中，基因i被检测到c多次。

我的问题是与更常用于此类数据的稀疏矩阵格式相比，count-min 草图需要多少内存。作为替代方案的一个简单示例，考虑一个哈希表——比如说，一个 Python 字典——存储每个不同的值c和 的对应值的总和i。如果在给定的细胞中观察到 n 个不同的基因，那么这需要 O(n) 空间。这个答案解释说，为了存储 n 个不同基因的计数，count-min 草图也需要 O(n) 空间。（基因的标识符作为字符串数组单独存储。）

我不明白为什么有人会为压缩似乎没有任何改进而引入如此多的复杂性。我也不明白这个应用程序有什么特别之处，当它对许多其他目的有用时，它会使 count-min 草图变得无用。所以：

• 对于这个应用程序，count-min 草图是否比典型的稀疏矩阵存储方案节省空间？
• 与典型的稀疏矩阵存储方案相比，count-min 草图是否有任何应用程序可以节省空间？如果是这样，与此应用程序的主要区别是什么？

什么是count-min 草图？在什么情况下会有用？

所以我最近才知道这些，但据我了解，计数布隆过滤器与计数分钟草图非常相似。不同之处在于前者对所有散列函数使用单个数组，而后者对每个散列函数使用一个数组。

如果为每个散列函数使用单独的数组将导致更少的冲突并减少误报，那么为什么没有这样实现计数布隆过滤器？