algorithm - 输出 AMS Sketch 和 Count Sketch 算法的区别

Question

我试图了解 AMS sketch 和 Count Sketch 算法之间的区别。我的理解是他们的目标/输出都是返回一个草图，这是一个频率向量。它包含经过的 Steam 中元素的频率。两者有什么区别？

从直觉上讲，AMS 算法仅指示元素是否经过，并不实际计算次数。虽然我不确定这是否正确。

此外，我不确定为什么首先需要草图。为什么不使用一个普通字典，每次元素散列到字典中的某个值时都会增加一个计数器？

希望这是有道理的。谢谢

Answer 1

两者都试图解决涉及保留比您实际可以放入字典中的更多元素的计数的问题。你不可能这样做，但你可以解决一些错误率的相关问题。

AMS 草图试图解决正确估计各种聚合统计量的问题。比如频率的平方和。

计数草图试图解决正确估计个体计数的问题。因此，在任何时候，您都可以采用您可能已经看到的任何特定值，并估算您已经看到它的次数。该估计是无偏的，高或低的可能性均等。

count-min sketch 与 count sketch 类似，不同之处在于它提供了您看过它的次数的上限。 (“最小值”是指您在算法中采用的最小值。)