data-structures - count-min 草图是否比典型的稀疏矢量格式占用更少的空间？

Question

count-min 草图是一种概率数据结构，用于多集中计数的有损存储。它接收更新 (i, c)哪里i是集合的一个元素并且 c是该元素的非负数，然后用散列函数做一些聪明的事情。它在 SO 和其他地方被广泛讨论；这是原始论文( PDF )和 Wikipedia article .基于我正在考虑的应用程序——来自单细胞基因组学实验的计数数据的有损存储——让我们假设 i和 c都是整数。对i,c表示在给定的生物细胞中，基因 i检测到 c次。
我的问题是，与更常用于此类数据的稀疏矩阵格式相比，count-min 草图需要多少内存。对于替代方案的一个简单示例，请考虑一个哈希表——比如一个 Python 字典——存储 c 的每个不同值。与 i 的相应值之和.如果在给定的细胞中观察到 n 个不同的基因，那么这需要 O(n) 空间。 This answer解释说，为了存储 n 个不同基因的计数，count-min 草图也需要 O(n) 空间。 (基因的标识符作为字符串数组单独存储。)
我不明白为什么有人会为似乎没有改进压缩的东西引入如此多的复杂性。我也不明白这个应用程序有什么特别之处，当它对许多其他目的有用时，它会使 count-min 草图变得无用。所以:

对于此应用程序，count-min 草图是否比典型的稀疏矩阵存储方案节省空间？

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

Answer 1

Count-min 草图主要(但不总是)用于尝试在数据流中查找最频繁项的应用程序。这个想法是，由于 count-min 草图(通常)会人为地提高每个项目的表观频率，如果一个项目具有很高的频率，那么当您从 count-min草图，但如果一个项目的频率较低，它将有一个更大但仍然较低的频率估计。
这使得 count-min 草图成为在 Google 上查找最受欢迎的搜索或在亚马逊上查看最多的项目等情况的绝佳选择。与传统哈希表相比，您可以将 count-min 草图配置为使用很少的空间 - 您需要多少空间取决于您，因为您可以根据可用内存调整准确性和置信度参数 - 并且仍然有信心在你得到的估计中。
另一方面，如果您正在开发一个应用程序，在该应用程序中存储您存储的每个项目的真实计数很重要，或者需要识别低频项目，那么最小计数草图不是真的会帮助这么多。为此，你真的没有太多可以改进的，比如哈希表。
请记住，一般来说，没有办法无损压缩任意频率的数据。 count-min 草图可以很好地用于查找频繁项的原因是它可以承受丢失所有低频元素的精确计数。这不适用于跟踪低频元素，因为通常情况下，低频元素比高频元素多得多，而丢弃高频元素不会减少太多的数据大小。
所以你的问题的答案是“这取决于你在做什么。”如果您的应用程序需要精确计数并且高估频率真的很糟糕，那么只需使用常规哈希表即可。如果您只是在寻找最常见的基因，那么 count-min 草图可能是一个不错的选择。