解释计数草图算法

Question

有人可以解释计数草图算法的工作原理吗？例如,我仍然无法弄清楚如何使用哈希.我很难理解这篇论文.

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,s Y的总和的变化在哪里a,并且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

计算草图是一种概率数据结构,可让您回答以下问题:

读取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 成对独立散列函数.这些复杂的词语意味着它们不会经常发生碰撞(事实上,如果两个哈希值都将值映射到空间[0, m]上,则碰撞的概率大致相同1/m^2).这些散列函数中的每一个都将值映射到空间[0, w].所以你创建一个d * w矩阵.

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

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

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