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

Question

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 草图是否有任何应用程序可以节省空间？如果是这样，与此应用程序的主要区别是什么？

标签： data-structuressparse-matrixcount-min-sketchprobabilistic-ds

Answer 1

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

这使得 count-min 草图成为诸如在 Google 上查找最受欢迎的搜索或在 Amazon 上查找最多的商品等情况的绝佳选择。与传统哈希表相比，您可以配置 count-min 草图以使用非常少的空间 - 确切需要多少空间取决于您，因为您可以根据可用内存调整准确性和置信度参数 - 并且仍然有信心在你得到的估计。

另一方面，如果您正在开发一个应用程序，其中存储您存储的每个项目的真实计数很重要，或者需要识别低频项目，那么 count-min 草图不是真的会帮助很多。为此，您确实无法对哈希表等进行改进。

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

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