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