解释计数草图算法

Question

有人可以解释计数草图算法的工作原理吗？例如，我仍然无法弄清楚如何使用哈希。我很难理解this paper。

Answer 1

此流式算法实例化以下框架。

1. 找到随机化的流算法，其输出（作为随机变量）具有期望的期望但通常是高方差（即，噪声）。
2. 要减少方差/噪声，请并行运行多个独立副本并组合其输出。

通常1比2更有趣。这个算法的2实际上有点不标准，但我只会谈论1。

假设我们正在处理输入

a b c a b a .

有三个计数器，没有必要哈希。

a: 3, b: 2, c: 1

但是我们假设我们只有一个。 h : {a, b, c} -> {+1, -1}有八种可能的功能。这是结果表。

 h  |
abc |  X = counter
----+--------------
+++ | +3 +2 +1 =  6
++- | +3 +2 -1 =  4
+-- | +3 -2 -1 =  0
+-+ | +3 -2 +1 =  2
--+ | -3 -2 +1 = -4
--- | -3 -2 -1 = -6
-+- | -3 +2 -1 = -2
-++ | -3 +2 +1 =  0

现在我们可以计算出期望

            (6 + 4 + 0 + 2) - (-4 + -6 + -2 + 0)
E[h(a) X] = ------------------------------------ = 24/8 = 3
                             8

            (6 + 4 + -2 + 0) - (0 + 2 + -4 + -6)
E[h(b) X] = ------------------------------------ = 16/8 = 2
                             8

            (6 + 2 + -4 + 0) - (4 + 0 + -6 + -2)
E[h(c) X] = ------------------------------------ =  8/8 = 1 .
                             8

这里发生了什么？对于a，比方说，我们可以分解X = Y + Z，其中Y是as总和的变化，而Z是非as的总和。通过期望的线性，我们有

E[h(a) X] = E[h(a) Y] + E[h(a) Z] .

E[h(a) Y]是a每次出现的一个词，即h(a)^2 = 1，所以E[h(a) Y]是a的出现次数。另一个词E[h(a) Z]为零;即使给出h(a)，每个其他哈希值也可能是正负1，因此在期望中贡献为零。

事实上，哈希函数不需要是统一随机的，而且好处：没有办法存储它。散列函数是成对独立的（任何两个特定散列值是独立的）就足够了。对于我们的简单示例，随机选择以下四个函数就足够了。

abc

+++
+--
-+-
--+

我会把新计算留给你。

Answer 2

计数草图是一个probabilistic data structure，它允许您回答以下问题：

阅读元素a1, a2, a3, ..., an的流可以有很多重复的元素，在任何时候它会给你以下问题的答案：到目前为止你看到了多少ai元素。

---

你可以清楚地获得一个确切的值，只需保持键是你的ai的哈希值，值是你到目前为止看到的元素数量。它是快速O(1)添加，O(1)检查，它给你一个确切的计数。唯一的问题是它需要O(n)空间，其中n是不同元素的数量（请记住，每个元素的大小有很大的不同，因为它需要way more space to store this big string as a key而不仅仅是this。

---

那么Count sketch会如何帮助你？与所有概率数据结构一样，您牺牲了空间的确定性。计算草图允许您选择2个参数：结果的精度ε和不良估计的概率δ。

要做到这一点，你选择一个d pairwise independent hash functions家庭。这些复杂的词语意味着它们不会经常发生碰撞（事实上，如果两个哈希值都将值映射到空间[0, m]上，则碰撞的概率大约为1/m^2）。这些散列函数中的每一个都将值映射到空间[0, w]。所以你创建了一个d * w矩阵。

现在，当您读取元素时，您可以计算此元素的每个d哈希值，并更新草图中的相应值。这部分与Count sketch和Count-min sketch相同。

Insomniac很好地解释了计数草图的想法（计算期望值），所以我只想用count-min来说明一切都更简单。您只需计算要获取的值的d哈希值，然后返回最小值。令人惊讶的是，这提供了强大的准确性和概率保证，你可以find here。

增加散列函数的范围，增加结果的准确性，增加散列的数量会降低错误估计的概率：ε= e / w和δ= 1 / e ^ d。另一个有趣的事情是价值总是被高估（如果你发现了价值，它很可能大于实际值，但肯定不会更小）。

Answer 3

事实上，哈希函数不需要是统一随机的，而且好处：没有办法存储它。散列函数是成对独立的（任何两个特定散列值是独立的）就足够了。对于我们的简单示例，随机选择以下四个函数就足够了。