有人可以解释计数草图算法的工作原理吗？例如，我仍然无法弄清楚如何使用哈希。我很难理解这篇论文。
问问题
17286 次
2 回答
52
此流式算法实例化以下框架。
找到一种随机流算法，其输出（作为随机变量）具有期望的期望，但通常具有高方差（即噪声）。
为了减少方差/噪声，并行运行许多独立副本并组合它们的输出。
通常 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]aE[h(a) Z]h(a)
事实上，散列函数不需要是均匀随机的，而且好消息是：没有办法存储它。散列函数成对独立就足够了（任何两个特定的散列值都是独立的）。对于我们的简单示例，以下四个函数的随机选择就足够了。
abc
+++
+--
-+-
--+
我会把新的计算留给你。
于 2011-07-25T04:20:25.050 回答
33
Count Sketch 是一种概率数据结构，可让您回答以下问题：
读取一个元素流a1, a2, a3, ...，an其中可能有很多重复元素，你随时可以回答以下问题：到目前为止，你看到了多少个元素？ai
您可以在任何时候清楚地得到准确的答案，只需维护ai您迄今为止看到的那些元素的数量的映射。记录新观察的成本为O(1)，检查给定元素的观察计数也是如此。但是，存储此映射需要O(n)空间，其中n是不同元素的数量。
Count Sketch 将如何帮助您？与所有概率数据结构一样，您牺牲了空间的确定性。Count Sketch 允许您选择两个参数：结果的准确性 (ε) 和错误估计的概率 (δ)。
为此，您选择d 成对独立的散列函数族。这些复杂的词意味着它们不会经常发生碰撞（事实上，如果两个哈希都将值映射到空间[0, m]则碰撞概率大约为1/m^2）。这些哈希函数中的每一个都将值映射到空间[0, w]，因此您创建了一个d * w矩阵。
当您读取元素时，您计算该元素的每个d哈希并更新草图中的相应值。这部分与 Count Sketch 和 Count-min Sketch 相同。
Insomniac 很好地解释了 Count Sketch 的想法（计算期望值），所以我会注意到使用 Count-min Sketch 一切都变得更加简单。您只需计算要获取的值的d个哈希值并返回其中的最小值。令人惊讶的是，这提供了强大的准确性和概率保证，您可以在此处找到。
增加散列函数的范围会提高结果的准确性，而增加散列的数量会降低错误估计的概率： ε = e/w和δ=1/e^d。另一个有趣的事情是价值总是被高估（如果你找到了价值，它很可能比实际价值大，但肯定不会更小）。
于 2016-02-12T06:22:35.847 回答