count-min sketch 是否比典型的稀疏向量格式花费更少 space？
Does the count-min sketch take less space than a typical sparse vector format?
count-min sketch 是一种概率数据结构，用于有损存储多集中的计数。它接收更新 (i, c)，其中 i 是集合的一个元素，c 是该元素的一个非负数，然后用哈希函数做一些聪明的事情。它在 SO 和其他地方被广泛讨论；这是原始论文（PDF) and the Wikipedia article。基于我正在考虑的应用——单细胞基因组学实验计数数据的有损存储——我们假设 i 和 c 是两个整数。i,c 对表示在给定的生物细胞中，基因 i 被检测到 c 次。
我的问题是与更常用于此类数据的稀疏矩阵格式相比，count-min 草图占用多少内存。对于替代方案的一个简单示例，考虑一个散列 table——比如说，一个 Python 字典——存储 c 的每个不同值以及 [=12] 的相应值的总和=].如果在给定细胞中观察到 n 个不同的基因，那么这需要 O(n) space。 This answer 解释说，为了存储 n 个不同基因的计数，计数最小草图也需要 O(n) space。 （基因的标识符作为字符串数组单独存储。）
我不明白为什么有人会在压缩方面似乎没有改进的情况下引入如此多的复杂性。我也不明白这个应用程序有什么特别之处，它会使 count-min 草图在用于许多其他目的时变得无用。所以：
- 对于此应用程序，count-min sketch 是否比典型的稀疏矩阵存储方案节省 space？
- 与典型的稀疏矩阵存储方案相比，count-min sketch 是否可以节省 space 的任何应用程序？如果是，与此应用程序的主要区别是什么？
Count-min 草图主要但不总是用于您试图在数据流中查找最频繁项的应用程序。这个想法是，由于 count-min 草图（通常）会人为地提高每个项目的表观频率，如果一个项目具有高频，那么当您从 count-min 草图，但如果一个项目的频率较低，它会有更大但仍然 low-ish 的频率估计。
这使得 count-min 草图成为在 Google 上寻找最受欢迎的搜索或在亚马逊上找到 most-viewed 商品等情况的绝佳选择。与传统散列 table 相比，您可以将 count-min 草图配置为使用很少的 space - 具体需要多少 space 取决于您，因为您可以调整基于您的可用内存的准确性和置信度参数 - 并且仍然对您得到的估计充满信心。
另一方面，如果您正在开发一个应用程序，其中存储每个项目的真实计数很重要，或者 low-frequency 个项目需要这样识别，那么count-min sketch 并没有多大帮助。为此，你真的没有太多可以改进的地方，比如说，哈希 table.
请记住，一般来说，没有办法无损地压缩任意频率数据。 count-min sketch 可以很好地查找频繁项的原因是它可以承受丢失所有 low-frequency 元素的精确计数。这不适用于跟踪 low-frequency 元素，因为通常 low-frequency 元素比 high-frequency 元素多得多，丢弃 high-frequency 元素不会减少数据大小这么多。
所以你的问题的答案是“这取决于你在做什么。”如果您的应用程序需要精确计数并且高估频率真的很糟糕，只需使用常规哈希 table。如果您只是寻找最常见的基因，那么 count-min 草图可能是个不错的选择。
作为我自己问题的替代答案：我想我误解了我链接到的答案。与我的问题的前提相反，它从未声明 [=12=] 草图采用 O(n) space。 space 要求取决于所需的精度。
count-min sketch 是一种概率数据结构，用于有损存储多集中的计数。它接收更新 (i, c)，其中 i 是集合的一个元素，c 是该元素的一个非负数，然后用哈希函数做一些聪明的事情。它在 SO 和其他地方被广泛讨论；这是原始论文（PDF) and the Wikipedia article。基于我正在考虑的应用——单细胞基因组学实验计数数据的有损存储——我们假设 i 和 c 是两个整数。i,c 对表示在给定的生物细胞中，基因 i 被检测到 c 次。
我的问题是与更常用于此类数据的稀疏矩阵格式相比，count-min 草图占用多少内存。对于替代方案的一个简单示例，考虑一个散列 table——比如说，一个 Python 字典——存储 c 的每个不同值以及 [=12] 的相应值的总和=].如果在给定细胞中观察到 n 个不同的基因，那么这需要 O(n) space。 This answer 解释说，为了存储 n 个不同基因的计数，计数最小草图也需要 O(n) space。 （基因的标识符作为字符串数组单独存储。）
我不明白为什么有人会在压缩方面似乎没有改进的情况下引入如此多的复杂性。我也不明白这个应用程序有什么特别之处，它会使 count-min 草图在用于许多其他目的时变得无用。所以：
- 对于此应用程序，count-min sketch 是否比典型的稀疏矩阵存储方案节省 space？
- 与典型的稀疏矩阵存储方案相比，count-min sketch 是否可以节省 space 的任何应用程序？如果是，与此应用程序的主要区别是什么？
Count-min 草图主要但不总是用于您试图在数据流中查找最频繁项的应用程序。这个想法是，由于 count-min 草图（通常）会人为地提高每个项目的表观频率，如果一个项目具有高频，那么当您从 count-min 草图，但如果一个项目的频率较低，它会有更大但仍然 low-ish 的频率估计。
这使得 count-min 草图成为在 Google 上寻找最受欢迎的搜索或在亚马逊上找到 most-viewed 商品等情况的绝佳选择。与传统散列 table 相比，您可以将 count-min 草图配置为使用很少的 space - 具体需要多少 space 取决于您，因为您可以调整基于您的可用内存的准确性和置信度参数 - 并且仍然对您得到的估计充满信心。
另一方面，如果您正在开发一个应用程序，其中存储每个项目的真实计数很重要，或者 low-frequency 个项目需要这样识别，那么count-min sketch 并没有多大帮助。为此，你真的没有太多可以改进的地方，比如说，哈希 table.
请记住，一般来说，没有办法无损地压缩任意频率数据。 count-min sketch 可以很好地查找频繁项的原因是它可以承受丢失所有 low-frequency 元素的精确计数。这不适用于跟踪 low-frequency 元素，因为通常 low-frequency 元素比 high-frequency 元素多得多，丢弃 high-frequency 元素不会减少数据大小这么多。
所以你的问题的答案是“这取决于你在做什么。”如果您的应用程序需要精确计数并且高估频率真的很糟糕，只需使用常规哈希 table。如果您只是寻找最常见的基因，那么 count-min 草图可能是个不错的选择。
作为我自己问题的替代答案：我想我误解了我链接到的答案。与我的问题的前提相反，它从未声明 [=12=] 草图采用 O(n) space。 space 要求取决于所需的精度。