计数-min草图比典型的稀疏向量格式占用的空间少吗？

Question

计数-最小草图是一种概率数据结构，用于在多个集合中对计数进行有损存储。它接收更新(i, c)，其中i是集合的元素，c是该元素的非负数量，然后使用哈希函数执行巧妙的操作。它在SO和其他地方都得到了广泛的讨论；这是原始论文(PDF格式)和维基百科文章。基于这个应用程序，我正在考虑用它来存储来自单细胞基因组学实验的计数数据--假设i和c都是整数。这对i,c意味着在一个特定的生物细胞中，基因i被检测到c次数。

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

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

• 对于这个应用程序，计数-min草图是否比典型的稀疏矩阵存储方案节省空间？
• 在典型的稀疏矩阵存储方案上，有哪种应用程序可以节省空间？如果是的话，与此应用程序的主要区别是什么？

Answer 1

Count草图主要(但不总是)在应用程序中使用，在这些应用程序中，您试图在数据流中查找最常见的项目。这个想法是，由于一个计数-min草图(通常)会人为地提高每个项目的表观频率，如果一个项目有一个高频率，当你从计数-min草图中得到估计值时，它总是有一个高频率，但是如果一个项目有一个低频，它会有一个更大但仍然很低的频率估计。

这使得在谷歌上找到最受欢迎的搜索或亚马逊上访问量最大的项目等情况下，“数分钟”草图的选择都是很好的。与传统的哈希表相比，您可以配置一个计数--最小的草图--使用非常小的空间--您需要多少空间，因为您可以根据可用的内存来调整精度和信任参数--并且仍然对您返回的估计值有信心。

另一方面，如果您正在开发一个应用程序，在这个应用程序中存储您存储的每个项目的真实计数非常重要，或者需要将低频项识别为这些项，那么count草图实际上不会对所有这些都有帮助。因此，实际上没有什么可以改进的，比如说，哈希表。

请记住，一般来说，没有办法无损地压缩任意频率的数据。计数-min素描之所以能很好地找到频繁的项目，是因为它可以丢失所有低频元素的精确计数。这不适用于跟踪低频元素，因为通常情况下，低频元素要比高频元素多得多，丢弃高频元素不会大大减少数据大小。

所以你的问题的答案是“这取决于你在做什么。”如果您的应用程序需要精确的计数，而且高估频率真的很糟糕，只需使用常规哈希表即可。如果你只是在寻找最常见的基因，那么一个计数-分钟草图可能是一个很好的选择。

Answer 2

作为我自己问题的另一个答案:我想我误解了我所联系的答案。与我的问题的前提相反，它从来没有说伯爵-最小草图占用O(n)空间。空间要求取决于所需的精度。