大数据亚线性空间算法

近似计数1

近似计数解决什么问题

    当数据特别大的时候,在二进制的条件下,存储一个数字N,需要log(N)的空间,如果N特别大而且这样的N又特别的多,该怎么办呢?
    我们的解决办法是行省一些准确性,从而节省更多的空间。使用近似计数算法,每一个数字的存储只需要loglog(N)的空间复杂度就行了。

流模型的计数问题

流模型

​ 定义一个数据流, \(i \in [1,m] , a_{i} \in [1,n]\),频率向量\(<fi>\),\(i \in [1,n] , f_{i} \in [1,m]\)。 ​ 数据流是无限的,当数据流流过m个时,出现了N个\(a_{i}\)。 ​ 请设计一个算法记录N的大小,要求空间复杂度为loglog(N)。

morris算法

算法

  1. 将X初始化为0

  2. 循环

    ​ 如果\(a_{i}\)出现一次 ​ ​ 就以\(1 / (2^{X})\)的概率将X增加1

  3. 返回\(\hat{f} = (2^{X} - 1)\)

证明的目标

​ 我们期望返回的值与N的差别尽量小,换句话说就是如果\(\hat{f}\)与N的差的绝对值大于某一个很小的值的概率很小,那么我们就可以用这种方法进行计数。说得更通俗一点就是使这个算法计算出的结果偏离N不多,或者偏离太多的概率特别小。

​ 利用切比雪夫不等式证明这一点\(P{[|X - \mu| \geq \epsilon]} \leqslant \sigma^{2}/\epsilon^{2}\)

证明

​ 计算期望\(E[2^{X_{N} } - 1] = N\)。(公式推导请见附录1)

​ 计算方差\(var[2^{X_{N} } - 1]\) = \(\frac{1}{2}N^{2}-\frac{1}{2}N\)。(公式推导请见附录2)

​ 令切比雪夫不等式中的\(X = Y = 2^{X_{N} }-1\)

​ 其中,\(X_{N}\)指的是\(X\)最终的值,下标指的是在这个计数器在流模型中经历了\(N\)个数字。则最终得到公式 \(P[|Y - N| \geq \epsilon ] \leqslant \frac{N^{2}-N}{2\epsilon^{2} }\)

​ 设定\(c = \frac{N^{2}-N}{2\epsilon^{2} }\),则可以将结果转化为该描述:\(X = E[x] \pm \sqrt{\frac{N^{2}-N}{2c} }\)(\(N\pm O(N)\))的概率是1 - c。

评价

​ 因为最终是通过记录\(X_{N}\)来反馈\(N\),而计算公式是\((2^{X_{N} } - 1)\),所以最终占用的空间复杂度是\(loglog(N)\)的。

​ 显而易见,模型的正确性并不好,并且随着N的增大误差和发生误差的概率也会变得越来越大。

关于近似计数有更加高效的算法morris+算法和morris++算法,将会在下一篇文章中与大家分享,敬请期待。

近似计数2

上一篇文章介绍了流模型,以及流模型中经典的计数问题,并给出了空间复杂度为\(loglog(N)\)\(morris\)算法,但是该算法仍有不足之处,这一点再上一篇中也已经指出了。这次给大家介绍两种基于\(morris\)

算法提出的改进算法\(morris+,morris++\)算法。

morris+算法

算法

  1. 运行k次morris算法
  2. 记录记录结果\((X_{1},...,X_{k})\)
  3. 返回\(\gamma = \frac{1}{k}\sum_{i = 1}^{k}(2^{X_{i} } - 1)\)

证明

​ 直接获取各个\(X_{i}\)对应的期望和方差,这在证明\(morris\)算法的时候已经计算过了。

​ 于是可以直接根据期望的性质计算期望\(E[\gamma] = N\)

​ 因为各个变量之间是相互独立的,所以可以利用独立变量之间方差的性质计算方差\(D[\gamma] = \frac{N^{2} - N}{2k}\)

​ 令切比雪夫不等式中的\(X\)\(\frac{1}{k}\sum_{i = 1}^{k}(2^{X_{i} } - 1)\),带入计算得\(P[|\gamma - N| \geq \epsilon] \leqslant \frac{N^{2}-N}{2k\epsilon^{2} }\),换一种描述就是,以\(1- c\)的概率,\(\gamma = N \pm \sqrt{\frac{N^{2}-N}{2kc} }\)或者\(N\pm \frac{O(N)}{\sqrt{k} }\)

评价

​ 当\(N\)确定时,如果想以0.9的概率满足近似标准,使\(c = 0.1\),则有\(k = \frac{5(N^{2} - N)}{\epsilon^{2} }\),我们会发现\(k = O(\frac{1}{\epsilon^{2} })\),这是你需要重复\(morris\)算法的次数。然而这么看代价也是不小的,因为这个算法为了保证准确性需要的\(k\)的个数并不少。

morris++算法

算法

  1. 重复morris+算法\(m = O(log(\frac{1}{\delta}))\)
  2. \(m\)个结果的中位数

算法目标

​ 前面已经证明过,为了得到\(1 - \delta\)下的\((1 + \epsilon)\)近似,使用\(morris+\)算法需要\(k = O(\frac{1}{\epsilon^{2} }\frac{1}{\delta})\)次计算,而\(morris++\)算法的工作就是将这一复杂度降低到了\(O(\frac{1}{\epsilon^{2} }log(\frac{1}{\delta}))\),说白了,也就是降低了计算次数。

证明的目标

​ 假设运行\(morris+\)算法时0.9的概率是正确的(正确指的是误差在允许范围之内)。

​ 从”中位数是正确的概率大于\(\delta\)“这一点出发推出最终需要的计算次数。

证明

​ 切尔诺夫不等式:\(X_{1},X_{2},...,X_{m}\)独立的\({0,1}\)变量,\(\mu = E[\sum_{i = 1}^{m}X_{i}],\epsilon \in [0,1]\)。则有:\(P[|\sum_{i = 1}^{m} - \mu| > \epsilon\mu] \leqslant 2e^{-\epsilon^{2}\mu/3}\)

​ 定义如果第\(i\)次运行计算正确,则\(X_{i} = 1\),也就是说\(E[X_{i}] = 0.9\)\(\mu = 0.9m\)

​ 当\(\sum{X_{i} } \geq 0.5m\)时,算法是正确的,简单理解,因为取的是中位数。这句话其实是一个条件,结合最终的目标,这个条件可以转化为\(P[\sum{X_{i} } < 0.5m] < \delta\)\[ \begin{align*} P[\sum{X_{i} } < 0.5m] &= P[\sum{X_{i} } - 0.9m < -0.4m]\\ &\leqslant P[|\sum{X_{i} } - \mu| > 0.4m]\\ &= P[|\sum{X_{i} } - \mu| > \frac{0.4}{0.9}\mu]\\ &\leqslant 2e^{-\frac{16}{81 \times 3}0.9m}\\ &\leqslant e^{-cm}这里的c就是一个常数,与上文不同\\ &< \delta \end{align*} \] ​ 最终通过最后一行的不等式\(e^{-cm}< \delta\),可以得到\(m = O(log(\frac{1}{\delta}))\)

评价

​ 通过一步一步的优化,最终只要进行\(O(log(\frac{1}{\delta}))\)次的计算就能保证\(1- \delta\)的正确率。

附录1

\(E[2^{X_{N} } - 1] = E[2^{X_{N} }] - 1\) \(E[2^{X_{N} }]\) \(= \sum_{i = 0}^{N}2^{i} *P[X_{N} = i]\) \(= \sum_{i = 0}^{N} \left \{(2^{i} - 1) * P[X_{N - 1} = i] + 2P[X_{N - 1} = i - 1] \right \}\) \(= \sum_{i = 0}^{N} \left \{2^{i} * P[X_{N - 1} = i] + 2P[X_{N - 1} = i - 1] - P[X_{N - 1} = i]\right \}\) \(= E[2^{X_{N - 1} }] + 1\) \(= E[2^{X_{0} }] + N\) \(= N + 1(E[2^{X_{0} }] = 1)\) \(E[2^{X_{N} } - 1] = N\)

附录2

\(\sigma^{2} = D[X] = E[X^{2}] - E[X]^{2}\) \(E[X^{2}] = E[4^{X_{N} } - 2^{x_{N} + 1} + 1]\) \(\sigma^{2} = D[X] = E[4^{X_{N} } - (N^{2} + 2*N + 1)\) \(E[4^{X_{N} }]\) \(= \sum_{i = 0}^{N}4^{i} *P[X_{N} = i]\) \(= \sum_{i = 0}^{N}\left \{4^{i} * P[X_{N - 1} = i] - 2^{i} * P[X_{N - 1} = i] + 2^{i + 1} * P[X_{N - 1} = i - 1]\right \}\) \(= \sum_{i = 0}^{N}\left \{4^{i} * P[X_{N - 1} = i]\right \} - \sum_{i = 0}^{N}\left \{ 2^{i} * P[X_{N - 1}= i]\right\} + \sum_{i = 0}^{N - 1}\left \{2^{i + 2} * P[X_{N - 1} = i]\right \}\) \(= E[4^{X_{N - 1} }] + 3N\) \(= \frac{3}{2}N^{2} + \frac{3}{2}N + 1\) \(\sigma^{2} = D[X] = \frac{1}{2}N^{2} - \frac{1}{2}N\)

不重复元素数1

解决什么问题

​ 还是流模型,这次解决的问题是计算一个流中不重复元素的个数。

​ 先回顾一下流模型,定义一个数据流\(<a_{i}>\)\(i \in [1,m] , a_{i} \in [1,n]\),频率向量\(<f_{i}>\)\(i \in [1,n] , f_{i} \in [1,m]\)

问题定义

​ 给定数据流\(\delta\),计算\(\sum_{1 \leqslant i \leqslant n}I[f_{i} > 0]\)\(I[f_{i} > 0] = 1\)当且仅当\(f_{i} > 0\)。说白了也就是计算不等于0,并且不重复的元素个数,相当于是相同的元素出现多次也记为出现一次。

FM算法

算法

  1. 随机选取一个哈希函数([0,1]上的均匀分布)\(h:[n] \mapsto [0,1]\)

  2. \(z = 1\)

  3. 当一个数字\(i\)出现的时候(循环)

    \(z = min\{z,h(i)\}\)

  4. 返回\(1 / z - 1\)

证明的目标 这一点与前面的\(morris\)算法是相似的,证明算法最终求出的结果偏离正确

结果的概率很小。

​ 利用切比雪夫不等式证明这一点\(P{[|X - \mu| \geq \epsilon]} \leqslant \sigma^{2}/\epsilon^{2}\)

证明

​ 令\(X = \frac{1}{z} - 1\)

​ 直接计算\(X\)的期望和方差是困难的,通过分母与分子转化和放缩实现范围的界定,证明过程中的\(d\)是真实情况下的解。

​ 计算\(E[z] = \frac{1}{d + 1}\)(计算过程见附录1)

​ 计算\(var[z] \leqslant \frac{2}{(d+1)(d+2)} < \frac{2}{(d+1)(d+1)}\)(计算过程见附录2)

​ 利用切比雪夫不等式\(P[|z - \frac{1}{d + 1}| > \epsilon \frac{1}{d + 1}] < var[z] / (\frac{\epsilon}{d+1})^{2} < \frac{2}{\epsilon^{2} }\)

​ 最终计算(关于第二步的放缩详见附录3): \[ \begin{align*} P[|X - d| > {\epsilon}'d]&= P[|\frac{1}{z} - (d + 1)| > {\epsilon}'d](calculate\ the\ range\ of\ z)\\ &\leqslant P[{|z - \frac{1}{d + 1}| > \frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}\frac{1}{d + 1} }]\\ s.t.\epsilon = \frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}\\ & < \frac{2}{\frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}^{2} }\\ & = 2(\frac{d + 1}{ {\epsilon}'d} + 1)^{2}\\ & < 2(\frac{2}{ {\epsilon}'} + 1)^{2} \end{align*} \] 评价

​ 从结果可以看出,最终的概率肯定是一个比1大的数字,所以在实际运行时仅仅使用这个算法是不行的,但是这个算法是接下来要介绍的算法的基础。在接下来,将会对更加高效的\(FM+\)算法、\({FM}'+\)算法等进行介绍。

附录1

​ 通过随机变量的分布函数和概率密度的关系进行计算。

\(F(x) = P(X < x),f(x) = {F}'(x)\),也就是分布函数的导数就是概率密度函数。

​ 计算中假设\(Z\)是随机变量,\(z\)是最终结果。附录2相同。 \[ \begin{align} F(z)& = P(Z \leq z)\\ & = 1 - P(Z \geq z)\\ & = 1 - P(\min_{1 \leq i \leq d}{X_{i} } \geq z)\\ & = 1 - \prod_{1 \leq i \leq d}{P(X_{i})}\\ & = 1 - {(1 - z)}^d \end{align} \]\(Z\)的真实含义就是所有哈希值中最小的一个,在上面的计算中体现为取\(min\),而其中的\(X_{i}\)则是每一个哈希值的取值对应的随机变量,总共\(d\)个,并且相互之间是独立的。 \[ \begin{align} f(z)& = {F}'(z) = d{(1 - z)}^{d - 1}\\ E[Z]& = \int_{0}^{1}zf(z)dz\\ & = d\int_{0}^{1}z{(1 - z)}^{d - 1}dz\\ & = d\int_{0}^{1}(1 - z){z}^{d - 1}dz\\ & = d[\int_{0}^{1}{z}^{d - 1}dz - \int_{0}^{1}{z}^{d}dz]\\ & = \frac{1}{d + 1} \end{align} \]

附录2

\(var[Z] \leq E[Z^2] = \frac{2}{(d+1)(d+2)}\)

​ 计算原理与期望相似。只需计算出分布函数即可,后面步骤相同。

​ 设\(U = Z^2\)\(G(u)\)\(U\)的分布函数,则 \[ \begin{align} G(u)& = P(U \leq u)\\ & = P(Z^2 \leq u)\\ & = P(Z \leq \sqrt{u})\\ & = F(\sqrt{u})\\ g(u)& = {(1 - \sqrt{u})}^{d - 1}\frac{d}{2\sqrt{u} }\\ E[u] & = \int_{0}^{1}ug(u)du\\ & = d\int_{0}^{1}{(1 - z)}^{d - 1}z^2dz\\ & = \frac{2}{(d+1)(d+2)} \end{align} \]

附录3

\[ \begin{align} & P[|\frac{1}{z} - (d + 1)| > {\epsilon}'d]\\ = & P[\frac{1}{z} - (d + 1) > {\epsilon}'d] + P[(d + 1) - \frac{1}{z} > {\epsilon}'d]\\ = & P[z < \frac{1}{d + 1 + {\epsilon}'d}] + P[z > \frac{1}{d + 1 - {\epsilon}'d}]\\ = & P[\frac{1}{d + 1} - z > \frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}] + P[z - \frac{1}{d + 1} > \frac{ {\epsilon}'d}{d + 1 - {\epsilon}'d}]\\ \leqslant & P[\frac{1}{d + 1} - z > \frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}] + P[z - \frac{1}{d + 1} > \frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}]\\ = & P[{|z - \frac{1}{d + 1}| > \frac{ {\epsilon}'d}{d + 1 + {\epsilon}'d}\frac{1}{d + 1} }]\\ \end{align} \]

不重复元素2

​ 上一篇文章已经向大家介绍了流模型的不重复元素的计数问题,并且详细讲解了用于解决该问题的\(FM\)算法,但是这个算法的弊端很明显,这次我来介绍基于\(FM\)的另外两个算法,更加高效的\(FM+\)算法、\({FM}'+\)算法。

\(FM+\)算法

多次运行\(FM\)算法

算法

  1. 总共运行q次\(FM\)算法
  2. 为每一次的运行随机选取一个哈希函数\(h_{j} : [n] \mapsto [0,1]\)
  3. 初始化\(z_{j} = 1\)
  4. 开始计数:每当\(i\)出现,更新\(z_{j} = min(z_{j},h_{j}(i))\)
  5. \(Z = \frac{1}{q}\sum_{j = 1}^{q}z_{j}\)
  6. 返回\(1 / Z - 1\)

证明的目标

​ 与\(FM\)算法相同,证明出错的该率在一定的范围之内,并且给出要满足一定的正确率需要的计算次数\(q\)的大小。

证明

\(FM\)算法相似,令\(X = \frac{1}{Z} - 1\)

​ 计算\(E[Z] = \frac{1}{d + 1}\),虽然进行了多次计算,但是多次计算时独立的,所以最终计算出的\(q\)个结果作为变量相互之间也是独立的。所以期望时不变的,下面的方差计算原理类似。

​ 计算\(var[Z] \leqslant \frac{2}{(d+1)(d+2)} \frac{1}{q} < \frac{2}{(d+1)(d+1)} \frac{1}{q}\)

​ 接下来的计算过程以及放缩的方法与\(FM\)算法完全相同,不再赘述。

​ 最终得到公式\(P[|X - d| > {\epsilon}'d]< \frac{2}{q}(\frac{2}{ {\epsilon}'} + 1)^{2}\)

评价

​ 从结果可以看出,\(q\)越大,也就是计算的次数越多,最终的结果也就约精确。如果我们要求最终的结果以\(1 - \delta\)的概率落在误差允许范围之内,则意味着\(\frac{2}{q}(\frac{2}{ {\epsilon}'} + 1)^{2} > \delta\),也就是\(q > O(\frac{1}{ { {\epsilon}'}^2\delta})\)

\({FM}'+\)算法

依然是多次计算,但是是另一种计算方法

算法

  1. 随机选取一个哈希函数\(h : [n] \mapsto [0,1]\)
  2. \((z_{1},z_{2},...,z_{k}) = 1\)也就是所有的\(z\)的初值都设置为1
  3. 维护当前看到的最小的\(k\)个哈希值
  4. 返回\(k / z_{k}\)

算法解释

​ 其实最终只运行了一次\(FM\)算法,但是记录了所有的值中最小的\(k\)个。

证明

\(P[|\frac{k}{z_{k} } - d| > \epsilon d] = P[\frac{k}{(1 + \epsilon)d} > z_{k}] + P[\frac{k}{(1 - \epsilon)d} < z_{k}]\)

第一步:

​ 接下来进行一些转换,\(\frac{k}{(1 + \epsilon)d} > z_{k}\),也就是至少有\(k\)个是比\(\frac{k}{(1 + \epsilon)d}\)小的,所以可以将公式中的第一项转换,第二项用同样的思路可以得到。

​ 为流中的每一个元素准备一个指示变量\(X_{i}\)\(X_{i} = 1 <=> h(i) < \frac{k}{(1 + \epsilon)d}\)

\(P[\frac{k}{(1 + \epsilon)d} > z_{k}] = P[\sum X_{i} \geq k]\)

​ 为流中的每一个元素准备一个指示变量\(\gamma_{i}\)\(\gamma_{i} = 1 <=> h(i) < \frac{k}{(1 - \epsilon)d}\)

\(P[\frac{k}{(1 - \epsilon)d} < z_{k}] = P[\sum \gamma_{i} < k]\)

第二步:

​ 计算\(E[\sum{X_{i} }] = \frac{k}{1 + \epsilon}\)

​ 计算\(Var[\sum{X_{i} }] < \frac{k}{1 + \epsilon}\)

​ 计算的原理非常简单,每一个指示变量都是\(\{0,1\}\)变量,只要计算值取1时的概率即可,这是简单的。

​ 同理计算\(E[\sum{\gamma_{i} }] = \frac{k}{1 - \epsilon}\)

​ 计算\(Var[\sum{\gamma_{i} }] < \frac{k}{1 - \epsilon}\)

第三步:

​ 利用切比雪夫不等式证明 \[ \begin{align*} P[\sum X_{i} \geq k] & = P[\sum X_{i} - \frac{k}{1 + \epsilon} \geq \frac{\epsilon k}{1 + \epsilon}]\\ & \leq \frac{1 + \epsilon}{ {\epsilon}^2k}\\ P[\sum \gamma_{i} < k] & = P[\frac{k}{1 - \epsilon} - \sum{\gamma_{i} } > \frac{\epsilon k}{1 - \epsilon}]\\ & < \frac{1 - \epsilon}{ {\epsilon}^2k} \end{align*} \] ​ 所以最终的结果就是\(P < \frac{2}{ {\epsilon}^2k}\)

评价

​ 最终的结果,我们假设结果以\(1 - \delta\)的概率落在误差允许范围之内,那么可以得到\(k = O(\frac{1}{ {\epsilon}^2\delta})\),我们发现最终两个算法实现的相同的效果,但是这个算法计算起来更加节约资源。

不重复元素3

​ 上一篇文章介绍了同样是应用于不重复元素计数问题的\(FM+\)算法、\({FM}'+\)算法,使用这两个算法只要计算总够多的次数,就能得到比较理想的结果。另外,在\(FM+\)算法的基础之上,我们还可以利用\(Median\)技术,进行改进,将最终的计算代价缩小为\(O(\frac{1}{ {\epsilon}^2}log\frac{1}{\delta})\),证明的方法依然是使切尔诺夫不等式,具体过程与前面讲过的算法雷同,不再赘述。

​ 这次来介绍两个利用\(zeros(h(j))\)的方法,\(Practical FM\)算法和\(BJKST\)算法。

准备知识

\(k-wise\ independent\ hash\ functions\)

​ 一个从\([a]\)映射到\([b]\)的哈希函数是\(k-wise\)的,如果\(\forall j_{1},...,j_{k} \in [b] and \forall j_{1},...,j_{k} \in [a],p[h(i_{1}) = j_{1} \wedge ...\wedge h(i_{k}) = j_{k}] = \frac{1}{b^k}\)

\(zeros(h(j))\)

\(zeros(h(j)) = max(i:p \% 2^{i} = 0)\)

​ 也就是展开成二进制后末尾0的个数,比如8对应的二进制是1000,则\(zeros(8) = 3\)

\(Practical FM\)算法

算法

  1. \(2-wise\ independent\)哈希函数族中随机选取\(h:[n] \mapsto [n]\)

  2. \(z = 0\)

  3. 如果\(zeros(h(j)) > z\)

    \(z = zeros(h(j))\)

  4. 返回\(\hat{d} = {2}^{z + \frac{1}{2} }\)

算法解释

​ 最终求出的\(z\)就是流中所有元素对应的哈希值的\(zeros\)值里面最大的那一个。

​ 该算法最终证明的目标就是以\(1 - \frac{2\sqrt{2} }{C}\)概率满足\(d / C \leq \hat{d} \leq Cd\)

证明

准备工作:

​ 设置指示变量\(X_{r,j} = 1 \Leftrightarrow zeros(h(j)) \geq r\)\(Y_{r} = \sum_{j:f_{j} > 0}{X_{r,j} }\)\(t\)是最后的\(z\)的值,\(t \geq r \Leftrightarrow Y_{r} > 0\)\(t \leq r \Leftrightarrow Y_{r + 1} = 0\)

​ 计算\(E[X_{r,j}] = \frac{1}{2 ^ r}\),简单理解,比如我现在要找二进制末尾有3个零的数字,如果我从1开始数,001、010、011、100、101、110、111、1000 ... ...,则每8个数字会出现一个,又每个数字出现的概率是相同的,则\(P[X_{r,j} = 1] = \frac{1}{2^r}\)近似成立。

​ 计算\(E[Y_{r}] = \frac{d}{2 ^ r}\),并将方差放缩至第一项,计算\(var[Y_{r}] \leq \frac{d}{2^r}\)

​ 利用马尔可夫不等式计算\(P[Y_{r} > 0] = P[Y_{r} \geq 1] \leq E[Y_{r}] / 1 = \frac{d}{2^d}\)

​ 利用切比雪夫不等式计算\(P[Y_{r} = 0] = P[|Y_{r} - E[Y_{r}]| \geq \frac{d}{2^d}] \leq \frac{2^r}{d}\)

​ 假设\(a\)是满足\(2^{a + 1 / 2} \geq Cd\)的最小整数,\(b\)是满足\(2^{b + 1 / 2} \leq \frac{d}{C}\)的最大整数。

最终计算:

\(P[\hat{d} \geq Cd] = P[t \geq a] = P[Y_{a} > 0] \leq \frac{d}{2^a} \leq \frac{\sqrt{2} }{C}\)

\(P[\hat{d} \leq d / C] = P[t \leq b] = P[Y_{b + 1} = 0]\leq\frac{\sqrt{2} }{C}\)

​ 上面计算出来的是错误的概率,则最终正确的概率应该大于\(1 - \frac{2\sqrt{2} }{C}\)

评价

​ 在使用时存储z就可以了,所以空间复杂度是\(O(loglogn)\)的。

​ 同样的,依然可以利用\(Median\)技术,做法依然和之前相同。

不重复元素4

​ 继续上一篇文章的内容,这次来介绍基于\(zeros(h(j))\)\(BJJKST\)算法。

\(BJKST\)算法

算法

  1. 随机选择2-wise independent哈希函数\(h:[n] \rightarrow [n]\)
  2. 随机选择2-wise independent哈希函数\(g:[n] \rightarrow [b\epsilon^{-4}log^2n]\)
  3. \(z = 0,B = \varnothing\)
    1. 如果\(zeros(h(j)) > z\)
      1. \(B = B \cup {(g(j),zeros(h(j)))}\)
      2. 如果 \(|B| > \frac{c}{\epsilon^2}\)
        1. \(z = z + 1\)
        2. \(B\)中删除\((\alpha,\beta)\),其中\(\beta < z\)

​ 4. \(return\ \hat{d} = |B|2^z\)

算法解释

​ 要想清楚地解释这个算法,只需要清楚两点即可。

​ 第一,\(B\)的变化,当出现的一个新的元素时,如果\(zeros(h(j)) > z\),则将相应的二元组插入到\(B\)中;如果\(B\)中的元素数量超过了某个大小,就将其中第二项小于\(z\)的元素从中删除。

​ 第二,\(z\)的变化,每当\(B\)的大小超出限制一次,\(z\)的值相应的就增加\(1\)

证明的目标

​ 该算法可以实现至少\(2/3\)概率保证\((1 + \epsilon)\)近似。

证明假设

​ 整个算法假设在\(B\)中存储的是在\(g\)下的哈希值,而不是元素本身,这样做不改变\(B\)

​ 以上是证明的假设,使用这个假设,造成的后果是有一些原来不同的元素比如\((\alpha,\beta1)\)\((\alpha,\beta2)\)本来是不同的元素,但是如果按照假设只考虑\(g\)的哈希值的话,那么两个元素就是相同的,我们把这个叫做\(g\)冲突。另外根据假设没有这样的冲突存在。那么最终就要构成一定的误差。针对于这一点,算法的证明者保证通过哈希函数的选取,可以将这一误差出现的概率限制在\(1 / 6\)内,也就是在最后算出来错误的概率之后,加上这个\(1 / 6\)就是最终的错误概率。

证明

​ 首先求在假设下的\(P[|\hat{d} - d| > \epsilon d]\)的范围。

​ 定义\(0,1\)指示变量\(X_{i,j} = 1 \Leftrightarrow zeros(h(j)) > r\)

​ 定义\(Y_{r} = \sum_{j:f_{j} > 0}{X_{i,j} }\)

​ 设\(t\)\(z\)的最终值,则\(Y_{t} = |B|\)\(\hat{d} = |B|2^t = Y_{t}2^t\)

​ 计算\(E[Y_{r}] = \frac{d}{2 ^ r}\)\(var[Y_{r}] \leq \frac{d}{2^r}\),关于计算过程在上一篇文章中有所介绍。

​ 通过将\(\hat{d} = Y_{t}2^t\)代入最初要求解的概率公式,并且考虑\(t\)的不同取值,得到公式\(P[FAIL] = P[|\hat{d} - d| > \epsilon d] = \sum_{r = 1}^{logn}P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r} \wedge t = r]\)

​ 接下来需对这个公式分析一下,假设事件\(A\)\(|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r}\),事件\(B\)\(t = r\)。求和变量\(r\)很小的时候,举个极端情况\(r = 0\),最终计算出来的结果肯定是完全正确的,这个可以对照着算法流程自己模拟一遍,道理是相似的,当\(r\)很小的时候,事件\(A\)发生的概率很小,所以这个时候\(P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r} \wedge t = r] < P[A]\),同样的道理,当\(r\)比较大的时候,\(B\)发生的概率就很小,这个时候\(P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r} \wedge t = r] < P[B]\)。关于这个放缩,肯定是发生概率小的那个事件是概率的限制,如果按照概率大的那个事件放缩,那么放缩造成的代价就太大了。这个时候,就需要一个临界点\(s\),当\(r < s\)时,使用第一种放缩,否则使用第二种。具体计算过程如下。 \[ \begin{align*} P[FAIL]& = P[|\hat{d} - d| > \epsilon d]\\ & = \sum_{r = 1}^{logn}P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r} \wedge t = r]\\ & < \sum_{r = 1}^{s - 1}P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r}] + \sum_{r = s}^{logn}P[t = r]\\ & = \sum_{r = 1}^{s - 1}P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r}] + P[t \geq s]\\ & = \sum_{r = 1}^{s - 1}P[|Y_{r} - \frac{d}{2 ^ d}| \geq \frac{\epsilon d}{2^r}] + P[Y_{s - 1} \geq \frac{c}{\epsilon ^ 2}]\\ & = \sum_{r = 1}^{s - 1}\frac{var[Y_{r}]}{(\epsilon d / 2 ^ r)^2} + \frac{E[Y_{s - 1}]}{c / \epsilon ^ 2}\\ & = \sum_{r = 1}^{s - 1}\frac{2 ^ r}{\epsilon ^ 2 d} + \frac{\epsilon ^ 2 d}{c2^{s - 1} }\\ & < \frac{2 ^ s}{\epsilon ^ 2 d} + \frac{\epsilon ^ 2 d}{c2^{s - 1} }\\ \end{align*} \] ​ 在得到了计算结果之后,我们发现还有两个参数没有标定,在标定了参数范围之后,就能进行计算最终的结果了。现选取参数范围如下\(\frac{12}{\epsilon ^ 2} \leq \frac{d}{2 ^ s} \leq \frac{24}{\epsilon ^ 2}\)\(c \geq 2 * 24 * 12\)。则最终\(P[FAIL] < 1 / 6\)

​ 再加上之前出去算法假设造成的错误概率,最终总的错误概率在\(1/3\)之内。

评价

​ 挺好的,哈哈。空间复杂度为\(O(logn + \frac{1}{\epsilon ^ 2}(log\frac{1}{\epsilon} + loglogn)\)

​ 至此,不重复元素问题已经介绍完了,接下来依然是空间算法的内容,品读估计、点查询等,敬请期待。

点查询1

解决什么问题

​ 再次介绍一下流模型,定义一个数据流\(<a_{i}>\)\(i \in [1,m] , a_{i} \in [1,n]\),频率向量\(<f_{i}>\)\(i \in [1,n] , f_{i} \in [1,m]\)

​ 仍然是流模型的相关问题,在之前已经介绍过了用于解决单个元素出现次数的近似计数问题,以及一个流中不重复元素的个数问题。这次要进行介绍的是一个流中所有的元素出现次数的计数问题,其实就是对计数问题的一个扩展,也就是对\([1,n]\)中的每一个数字在流中出现的次数进行计数,是一个相对更加高级的算法。

问题定义

点查询问题

​ 给定数据流\(\sigma\)\(a_{i}\),输出\(f_{i}\)\(i \in [1,n]\)

知识准备

范数

\(l_{p} = \left \| x \right \|_{p} = {(\sum_{i}{|x_{i}|^p})}^{\frac{1}{p} }\)

\(l_{p}\)点查询(频度估计)

​ 给定数据流\(\sigma\)\(a_{i}\)输出\(\hat{f_{i} }\)满足\(\hat{f_{i} } = f_{i} \pm \epsilon \left|| \textbf{f} \right||_{p}\)

\(\left|| x \right||_{1} \geq \left|| x \right||_{2} \geq ... \geq \left|| x \right||_{\infty}\)\(p\)越大,估计越准确

\(\left \| x \right \|_{0}\)是不同元素的数目

\(\left \| x \right \|_{1}\)是流的长度

\(\left \| x \right \|_{\infty}\)是最大频度

Misra_Gries算法

算法

维护一个集合\(A\),其中的元素是\((i,\hat{f_{i} })\)

  1. \(A \leftarrow \varnothing\)
  2. 对每一个数据流中的元素\(e\)
    1. 如果\(e \in A\),令\((e,\hat{f_{e} }) \rightarrow (e,\hat{f_{e} } + 1)\)
    2. 否则如果\(|A| < \frac{1}{\epsilon}\)
      1. \((e,1)\)插入\(A\)
    3. 否则将所有\(A\)中计数减\(1\)
      1. 如果\(\hat{f_{j} } = 0\),从\(A\)中删除\((j,0)\)
  3. 对于查询\(i\),如果\(i \in A\),返回\(\hat{f_{i} }\),否则返回\(0\)

证明的目标

​ 算法的过程是简单的,不再进行解释,对任意的查询\(i\),返回\(\hat{f_{i} }\)满足\(f_{i} - \epsilon m \leq \hat{f_{i} } \leq f_{i}\)

证明

​ 结合算法过程,总共有两种情况。

​ 如果不发生减\(1\)的情况,那么\(\hat{f_{i} } = f_{i}\),如果发生了减\(1\)的情况,有\(\hat{f_{i} } < f_{i}\),假设发生了\(c\)次减\(1\)的情况,总数减少\(\frac{c}{\epsilon} \leq m\),每个 计数至多减少\(c\)\(\hat{f_{i} } \geq f_{i} - c \geq f_{i} - \epsilon m\)

评价

​ 从结果可以看到,最终得到的结果一定不会超过真实值,并且算法的空间代价是\(O(\epsilon^{-1}logn)\)

Metwally算法

算法

维护一个集合\(A\),集合中的元素是\((i,\hat{f_{i} })\)

  1. \(A \leftarrow \varnothing\)
  2. 对每一个数据流中的元素\(e\)
    1. 如果\(e \in A\),令\((e,\hat{f_{i} }) \leftarrow (e,\hat{f_{i} } + 1)\)
    2. 否则如果\(|A| < \frac{1}{\epsilon}\)
      1. \((e,1)\)插入\(A\)
    3. 否则将\((e,MIN + 1)\)插入\(A\),并删除一个满足\(\hat{f_{e} } = MIN\)
  3. 查询\(i\),如果\(i \in A\),返回\(\hat{f_{i} }\),否则返回\(MIN\),注意这个\(MIN\)

证明的目标

​ 对任意的查询\(i\),返回\(\hat{f_{i} }\)满足\(f_{i} \leq \hat{f_{i} } \leq f_{i} + \epsilon m\)

证明

​ 与上一个的算法相似,也是两种情况。

​ 如果不发生删除的情况,那么\(\hat{f_{i} } = f_{i}\)。如果删除,计数一定不大于删除后的\(MIN\),有\(\hat{f_{i} } \geq f_{i}\)\(A\)中元素总是\(m\)\(MIN \frac{1}{\epsilon} \leq m \Rightarrow MIN \leq \epsilon m\),每个元素至多超出真实值\(MIN\)\(\hat{f_{i} } \leq f_{i} + \epsilon m\)

评价

​ 与上一个算法刚好相反,这里的最终结果一定不会小于真实值,并且算法的空间代价是\(O(\epsilon^{-1}logn)\)

点查询2

定义流模型

​ 之前讲的流模型只具备增加功能,这次扩大流模型的定义,从而使其也能支持删除操作。定义如下:

\(A\ stream\ includeing\ deletion\sigma = <\pm a_{1},...,\pm a_{m}>,a_{i} \in [n],then\ we\ can\ define\ a\ frequency\ vector\ f = (f_{1},...,f_{n})\)

​ 符号化的表示变化的过程就是:每次更新\((i,\Delta)\)使得\(x_{i} \leftarrow x_{i} + \Delta\)\(\Delta = 1\)就是之前所用的流模型。现在\(\Delta = \pm 1\),就能支持删除操作了。下面是几种经典的流模型以及其对应的名字:\(Vanilla\)模型对应\(\Delta = 1\)\(Cash\ Register\)模型对应\(\Delta > 0\)\(Turnstile\)对应\(\Delta = \pm 1\)

新的问题

​ 之前分析的\(Misra-Gries\)\(Metwally\)算法不支持数据流连接,符号化的表述就是无法根据\(\delta_{1}\)\(\delta{2}\)的结果计算\(\delta_{1}\delta_{2}\)的结果。

新的定义

Sketch

​ 定义在数据流\(\sigma\)上的数据结构\(DS(\sigma)\)是一个\(Sketch\),如果存在一个\(Space-Efficient\)的合并算法\(COMB\)使得\(COMB(DS(\sigma_{1}),DS(\sigma_{2})) = DS(\sigma_{1} \circ \sigma_{2})\),其中\(\circ\)是数据流的连接操作。

Linear Sketch

​ 定义在\([n]\)上的数据流\(\sigma\)上的\(sketching\)算啊输出\(sk(\sigma)\),如果\(sk(\sigma)\)取值为维度\(l = l(n)\)的向量,并且是\(f(\sigma)\)的线性函数,那么\(sk(\sigma)\)是一个\(Linear Sketch\)\(l\)是这个\(sketch\)的维度。

Count-Min Sketch算法

算法

  1. \(C[1...t][1...k] \leftarrow \textbf{0},k = \frac{2}{\epsilon},t = \left \lceil log\frac{1}{\delta} \right \rceil\)
  2. 随机选择\(t\)\(2-wise\)独立哈希函数\(h_{i}:[n] \rightarrow [k]\)
  3. 对每一个出现的更新\((j,c)\)进行如下操作
    1. \(for\ i = 1\ to\ t\)
      1. \(C[i][h_{i}(j)] = C[i][h_{i}(j)] + c\)
  4. 针对对于\(a\)的查询,返回 \(\hat{f_{a} } = \min_{1 \leq i \leq t}{C[i][h_{i}(a)]}\)

算法解释

​ 在算法开始时,构造一个\(t\)\(k\)列的空数组,可以认为每一行是独立的,算法在运行时同时记录了\(t\)个这样的数组。在每出现一个流数据的时候,对每一个数组进行一次更新,注意元素的第二个下标用的是数据的哈希值。

​ 算法在运行的过程中可能产生冲突,也就是两个不同的流数据的哈希值可能相同,这个时候就会导致结果偏大,但是因为有相当于\(t\)次的重复计算,通过取最小值的方法来进行一些弥补,但是这样的方法也不能完全避免冲突。

证明目标

​ 该算法以\(1 - \delta\)概率给出\(l_{1}\)点查询问题的\((1 + \epsilon)\)近似 ,具体地\(f_{a} \leq \hat{f_{a} } \leq f_{a} + \epsilon||\textbf{f}_{-a}||_{1}\),这里,\(||\textbf{f}_{-a}||_{1} = ||\textbf{f}||_{1} - f_{a}\)

证明

​ 给定一个流数据\(a\)\(Y_{ij} = 1 \Leftrightarrow h_{i}(j) = h_{i}(a)\),则\(C[i][h_{i}(a)] = \sum_{j}Y_{ij}f_{j} = f_{a} + \sum_{j \neq a} Y_{ij}f_{j}\)

​ 记\(z = \sum_{j \neq a} Y_{ij}f_{j}\)\(z\)是与\(i\)相关的,则\(E[z] = \sum_{j \neq a}E[Y_{ij}f_{j}]\),而\(E[Y_{ij}] = \frac{1}{k}\),所以\(E[z] = \frac{||\textbf{f}_{-a}||_{1} }{k}\)

​ 根据马尔可夫不等式,\(P[z \geq \epsilon||\textbf{f}_{-a}||_{1}] \leq \frac{E[z]}{\epsilon ||\textbf{f}_{-a}||_{1} } = \frac{1}{k\epsilon} = \frac{1}{2}\)

​ 接下来证明\(P[\hat{f_{a} } > f_{a} + \epsilon||\textbf{f}_{-a}||_{1}] \leq \delta\)

\(P[\hat{f_{a} } > f_{a} + \epsilon||\textbf{f}_{-a}||_{1}] = P[\hat{f_{a} - f_a > \epsilon||\textbf{f}_{-a}||_{1} }] = P[min{z_i} > \epsilon||\textbf{f}_{-a}||_{1}] = \prod_{i}P[z_i > \epsilon||\textbf{f}_{-a}||_{1}] \leq \frac{1}{2^t}\)

​ 因为最终的结果是一个\(1 - \delta\)的算法,所以只要令\(\delta = \frac{1}{2^t}\)就行了,这也正是\(t\)的值的来源。

评价

​ 算法的空间代价为\(O(\frac{1}{\epsilon}log\frac{1}{\delta}(logn + logm))\),针对\(Cash\ Register\)模型有近似质量保证。接下来将会介绍使用范围更加广泛的\(Count-Median\ Sketch\)算法。

点查询3

​ 这次介绍的是\(Count-Median\ Sketch\)算法,问题依然是流模型中的点查询问题,但是这次的流模型是\(Turnstile\),也就是每次的更新有正有负。

Count-Median Sketch算法

算法

  1. \(C[1...t][1...k] \leftarrow \textbf{0},k = \frac{2}{\epsilon},t = \left \lceil log\frac{1}{\delta} \right \rceil\)
  2. 随机选择\(t\)\(2-wise\)独立哈希函数\(h_{i}:[n] \rightarrow [k]\)
  3. 对每一个出现的更新\((j,c)\)进行如下操作
    1. \(for\ i = 1\ to\ t\)
      1. \(C[i][h_{i}(j)] = C[i][h_{i}(j)] + c\)
  4. 针对对于\(a\)的查询,令 \(|C[x][h_x(a)]| = median_{1 \leq i \leq t}{|C[i][h_{i}(a)]|}\)
  5. 返回\(\hat{f_a} = |C[x][h_x(a)]|\)

算法解释

​ 与\(Count-Min Sketch\)算法的计数方法完全一致,差别就在返回值的获取上,返回的是所有\(t\)个数组值的绝对值的中位数对应的原始值。

证明目标

​ 该算法以\(1 - \delta\)概率给出\(l_{1}\)点查询问题的\((1 + \epsilon)\)近似 ,具体地\(|\hat{f_a} - f_a| \leq \epsilon||\textbf{f}_{-a}||_{1}\),这里,\(||\textbf{f}_{-a}||_{1} = ||\textbf{f}||_{1} - f_{a}\)

证明

​ 关于\(z_i\)的定义在上一个算法的描述中已经进行了声明,

TODO

评价

​ 由于计数过程与上一个算法一样,所以空间代价也一样,并且针对\(Turnstile\)模型有近似质量保证,接下来将会介绍具有更好估计效果的\(Count Sketch\)算法以及他的\(Median\)版本。

点查询和频度估计4

Count Sketch算法

算法

  1. \(C[1...k] \leftarrow 0,k = \frac{3}{\epsilon^2}\)
  2. 随机选择1个\(2-wise\)独立哈希函数\(h:[n] \rightarrow [k]\)
  3. 随机选择1个\(2-wise\)独立哈希函数\(g:[n] \rightarrow \{-1,1\}\)
  4. 对于每一个更新\((j,c)\)
    1. \(C[h(j)] = C[h(j)] + c * g(j)\)
  5. 针对查询\(a\),返回\(\hat{f} = g(a) * C[h(j)]\)

证明目标

​ 算法针对\(Turnstile\)模型,以常数概率,有\((1 + \epsilon)\)近似。

证明

​ 令\(X = g(a) * C[h(a)]\),对结果进行化简,\(C[h(a)] = \sum_{j}g(j)f(j)Y(j)\),注意\(Y_j = 1 \Leftrightarrow h(j) = h(a)\),按照\(j\)\(a\)是否相同可以将结果划分为\(j == a\)\(j != a\)两个部分,所以最终\(X = f(a) + g(a)\sum_{j}g(j)f(j)Y_j\)

​ 计算\(E[X] = f(a) + g(a)\sum_{j \neq a}E[g(j)]f(j) = f(a)Y_j\)

​ 计算\(var[X] = \frac{||f_{-a}||_{2}^2}{k}\),计算过程见附录1,这里\(||f_{-a}||_{2} = \sqrt{||f||_2 - f_a^2}\)

​ 利用切比雪夫不等式\(P[|\hat{f_a} - f_a| > \epsilon ||f_{-a}||_{2}] \leq \frac{1}{k \epsilon^2} = \frac{1}{3}\)

评价

​ 我们最终得到常数概率\(\frac{2}{3}\),从最终的表达式中可以看出这个值是由\(k\)决定的,只要\(k\)足够大,就能得到很好的结果。并且该算法的空间代价是\(O(\frac{1}{\epsilon^2}(logn + logm))\)

Final Count Sketch算法

​ 利用\(Median\)技术对算法进行改进。

算法

  1. \(C[1...t][1...k] \leftarrow \textbf{0},k = \frac{3}{\epsilon^2},t = O(log\frac{1}{\delta})\)

  2. 随机选择1个\(2-wise\)独立哈希函数\(h_i:[n] \rightarrow [k]\)

  3. 随机选择1个\(2-wise\)独立哈希函数\(g_i:[n] \rightarrow \{-1,1\}\)

    1. 对于每一个更新\((j,c)\)
      1. 对于\(i : 1 \rightarrow t\)
        1. \(C[h_i(j)] = C[h_i(j)] + c * g_i(j)\)
  4. 返回\(\hat{f_a} = median_{1\leq i\leq t}g_i(a)C[i][h_i(a)]\)

算法解释

​ 相当于是将\(Count\ Sketch\)算法运行了\(t\)次,最后取了中值。利用齐尔诺夫不等式可以解决,令\(X_i = 1 \Leftrightarrow\)\(i\)次运行成功,成功概率是\(\frac{2}{3}\),最后只要成功的个数超过一半即可。最终是通过\(t\)控制了\(\delta\)

评价

​ 最终算法以\(1 - \delta\)概率给出了点查询问题的\(1 + \epsilon\)近似,\(|\hat{f_a} - f_a| \leq \epsilon||\textbf{f}_{-a}||_{2}\)

附录1

\[ \begin{align*} E[Y_j] &= \sum_{i = 1}^{k}P[h(a) = i \wedge h(j) = i] = \frac{1}{k}\\ E[g(i)g(j)] &= 1\ if\ i == j\ else\ 0\\ var[X] &= var[f(a) + g(a)\sum_{j \neq a}g(j)f(j)Y_j]\\ &= var[g(a)\sum_{j \neq a}g(j)f(j)Y_j]\\ &= E[(g(a)\sum_{j \neq a}g(j)f(j)Y_j)^2]\\ &= E[(\sum_{j \neq a}g(j)f(j)Y_j)^2]\\ &= E[(\sum_{i \neq a}g(i)f(i)Y_i)*(\sum_{j \neq a}g(j)f(j)Y_j)]\\ &= E[\sum_{i,j,i = j \neq a}(g(i)f(i)Y_i)*(g(j)f(j)Y_j)] + E[\sum_{i,j,i \neq j \neq a}(g(i)f(i)Y_i)*(g(j)f(j)Y_j)]\\ &= E[\sum_{j \neq a}(g(j)f(j)Y_j)^2]\\ &= E[\sum_{j \neq a}(f(j)Y_j)^2]\\ &= \sum_{j \neq a}f(j)E[(Y_j)^2]\\ &= \frac{||f_{-a}||_{2}^2}{k}\\ \end{align*} \]

​ 在计算的过程总要注意把握\(a,j\)\(h(a),h(j)\)的关系。

频度矩估计1

问题定义

​ 之前我们定义了不同的流模型,当\(\Delta\)取不同的值的时候对应着不同的模型以及不同的解决办法。在频度矩估计问题中,我们要解决的两类问题分别是\(\Delta = 1\)\(Vanilla\ Model\)\(\Delta > 0\)\(Cash\ Register\ Model\)

​ 一个数据流的第\(k\)阶频度矩表示为\(F_k(\sigma)\)或者\(F_k\)\(F_k = \sum_{i = 1}^{n}f_i^k = ||\textbf{f}||_k^k\)

​ 其实这个问题是一个高度概括的问题,与之前的很多问题都有很好的对应关系,当\(k = 0\)时,就是不重复元素的数目,\(k = 1\)就是计数问题,\(k = 2\)就是关系数据自连接。

​ 在这一部分中将会介绍\(AMS\)算法,为\(F_k(k \geq 2)\)估计问题提供亚线性空间的算法。总共是四个算法,他们分别是\(Basic\ AMS,Final AMS,Basic\ F_2\ AMS\)算法以及相应的\(Median\)改进版本。

​ 今天首先来介绍\(Basic\ AMS\)算法。

Basic AMS算法

算法

  1. \((m,r,a) \leftarrow (0,0,0)\)
  2. 对于每一个更新\(j\)
    1. \(m \leftarrow m + 1\)
    2. \(\beta \leftarrow 1\ with\ probability \frac{1}{m}\)
    3. 如果\(\beta == 1\)\(a = j,r = 0\)
    4. 如果\(j == a\)\(r \leftarrow r + 1\)
  3. 返回\(X = m(r^k - (r - 1)^k)\)

算法分析

​ 计算\(E[X] = F_k\),计算见附录1

​ 计算\(Var[X] \leq kn^{1 - \frac{1}{k} }F_k^2\),计算见附录2

​ 利用切比雪夫不等式对结果进行检验\(P[|X - E[x]| > \epsilon E[X]]<\frac{kn^{1 - \frac{1}{k} } }{\epsilon^2}\)

评价

​ 算法的方差太大,需要进一步的改进,但是其相应的存储代价为\(O(logm + logn)\)

附录1

​ 记\(A\)为算法返回时的\(a\)的值,相应的\(r\)的值记为\(R\)

​ 则\(A\)的取值为\(1,...,n\)\(R\)的取值为\(1,...,f_j\)

​ 计算两个概率:\(P[A = j] = \frac{f_j}{m}\)

​ 在一个数据流\(<a_1,a_2,...,a_m>\)中,最后的\(A = a_i,i \in [1,m]\)(注意这里的相等可以理解为java中的地址相同,而不是值相同)的概率计算思路为:在\(a_i\)对应的迭代中,\(a\)\(\frac{1}{i}\)的概率被更新为\(a_i\),然后在后面所有的迭代中都没有发生改变,这个过程用概率来表示就是\(\frac{1}{i} * (1 - \frac{1}{i + 1}) * ... * (1 - \frac{1}{m}) = \frac{1}{m}\)。所以\(P[A = a_i] = \frac{1}{m}\),所以自然而然的\(P[A = j] = \frac{f_j}{m}\)

​ 计算的思想相似可以得到\(P[R = i \wedge A = j] = \frac{1}{m}\)

​ 也就是\(P[R = i|A = j] = P[R = i \wedge A = j] / P[A = j] = \frac{1}{f_j}\) \[ \begin{align*}E[X] &= \sum_{j = 1}^{n}E[m(R^k - (R - 1)^k)] * P[A = j]\\&= \sum_{j = 1}^{n}\frac{f_j}{m}\sum_{i = 1}^{f_j}m(i^k - (i - 1)^k)\frac{1}{f_j}\\&= F_k\end{align*} \]

附录2

引理

\(kF_1F_{2k - 1} \leq k n^{1 - \frac{1}{k} }F_k^2\)

求解 \[ \begin{align*}Var[X] &\leq E[X^2]\\&= \sum_{j = 1}^{n}\sum_{i = 1}^{f_j}m(i^k - (i - 1)^k)^2\\&= \sum_{j = 1}^{n}\sum_{i = 1}^{f_j}m(i^k - (i - 1)^k)(i^k - (i - 1)^k)\\&= \sum_{j = 1}^{n}\sum_{i = 1}^{f_j}m(i^k - (i - 1)^k)k i^{k - 1}\\&\leq \sum_{j = 1}^{n}\sum_{i = 1}^{f_j}m(i^k - (i - 1)^k)k f_j^{k - 1}\\&= mkF_{2k - 1}\\&= kF_1F_{2k - 1}\\&\leq kn^{1 - \frac{1}{k} }F_k^2\\\end{align*} \]

频度矩估计2

问题分析

​ 使用\(Basic AMS\)算法的方差太大,直接利用\(Median\)技术也不能将最终的结果限制在\((1+\epsilon)\)中,所以要先用均值技术对结果进行优化,再取中位数,我们将这个方法叫做\(Median-of-Means\)

Final AMS 算法

算法

  1. 计算\(t = clog\frac{1}{\delta}\)个平均值
  2. 每个平均值是\(r = \frac{3k}{\epsilon ^ 2}n^{1 - \frac{1}{k} }\)次调用的平均值
  3. 返回\(t\)个数值的中间值

证明

​ 记\(\{X_{ij}\}_{i \in [t],j \in [r]}\)是与\(X\)独立同部分的随机变量集合。

\(Y_i = \frac{1}{r}\sum_{j = 1}^{r}X_{ij}\)

\(Z = \sum_{i = 1}^{t}Y_i\)

​ 计算\(E[Y_i] = E[X],Var[Y_i] = \frac{Var[X]}{k}\)

​ 根据切比雪夫不等式有\(P[|Y_i - E[Y_i]| \geq \epsilon E[Y_i]] \leq \frac{Var[X]}{k\epsilon^2E[X]^2}\)

​ 取值\(r = \frac{3Var[X]}{k\epsilon^2E[X]^2}\),将期望和方差带入可以计算得到算法中给出的结果

​ 现在\(P[|Y_i - E[Y_i]| \geq \epsilon E[Y_i]] \leq \frac{1}{3}\)

​ 最后利用\(Median\)技术进行处理即可。在前面已经有讲述,不再赘述。

评价

​ 算法的空间代价为\(O(\frac{1}{\epsilon^2}log\frac{1}{\delta}kn^{1 - \frac{1}{k} }(logm + logn))\),当\(k \geq 2\)时代价过大。

Basic \(F_2\) AMS 算法

算法

  1. 随机选择\(4-wise\)独立的哈希函数\(h:[n] \rightarrow \{-1,1\}\)
  2. \(x \leftarrow 0\)
  3. 对于每一个更新\((j,c)\)
    1. \(x \leftarrow x + c * h(j)\)
  4. 返回\(x^2\)

分析

​ 这个算法本身并没有什么比较好的效果,但是用过\(median-of-mean\)技术的优化,可以得到一个\((\epsilon,\delta)\)的算法。所以在这里的证明中,只计算出结果的期望和方差就行了。

证明

​ 记\(Y_j = h(j),j \in [1,n],X = \sum_{j = 1}^{n}f_jY_j\)

​ 计算\(E[X^2] = \sum_{i = 1}^{n}f_iY_i * \sum_{j = 1}^{n}f_jY_j\),处理的方法在之前已经介绍过,将\(i,j\)分为相等和不相等两种情况考虑,不相等时\(Y_iY_j\)的期望为\(0\)。所以最终的计算结果为\(F_2\),可以认为这个算法的运行结果是一个关于\(F_2\)的无偏估计。

​ 计算\(Var[X^2] = E[X^4] - E[X^2]^2\)

​ 计算\(E[X^4]\)的时候也要进行分类讨论,原理也还是一样的,稍微复杂一些,现在有四个独立随机变量,分四种情况考虑:四个完全相同,仅有三个相同,仅有两个相同,任何一个都不相同,对于相同的就不能当成独立变量了,而对于不相同的可以直接利用独立变量的期望公式得到结果是\(0\),所以最后只剩下两种情况:四个完全相同,仅有两个相同(两对两个相同[如果不理解直接看证明])。 \[ \begin{align*} E[X^4] &= E[\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{k = 1}^{n}\sum_{l = 1}^{n}f_iY_i*f_jY_j*f_kY_k*f_lY_l ]\\ &= F_4 + 3E[\sum_{i = 1}^{n}\sum_{j = 1,i \neq j}^{n}(f_iY_i)^2*(f_jY_j)^2]\\ &= F_4 + 3(F_2^2 - F_4)\\ \end{align*} \] ​ 所以\(Var[X^2] = 2(F_2^2 - F_4) \leq 2F_2^2\)

评价

​ 算法的空间代价是\(O(logm + logn)\),下面先使用\(mean\)将犯错概率限制在\(\frac{1}{3}\),再使用\(median\)技术对结果进行优化。

优化

​ 令\(t = clog\frac{1}{\delta},k = \frac{3Var[X^2]}{\epsilon^2E[X^2]^2} \leq \frac{6}{\epsilon ^ 2}\),其中\(k\)计算均值时的运行次数,可以使用切比雪夫不等式验证取了均值的结果犯错误的概率小于\(\frac{1}{3}\)了,再一次使用\(median\)技术进行优化,现在就是一个\((\epsilon,\delta)\)的算法了,它的空间代价为\(\tilde{O}(\epsilon^{-2}log{\frac{1}{\delta} })\)

总结

​ 至此已经介绍完了所有的频度矩估计算法,下面要介绍用于解决固定大小采样问题的水库抽样算法。

固定大小采样

问题定义

​ 假定每个时刻都有一个数据流中的一个数据到来,我们要维护 一个样本,这个样本动态更新,但是它时刻都是已经流过的数据的均匀抽样。

​ 我们通常使用水库抽样算法解决这个问题。

水库抽样算法

算法

  1. \(m \leftarrow 0\)
  2. 使用数据流的前\(s\)个元素对抽样数组进行初始化\(A[1,...,s],m\leftarrow s\)
  3. 对于每一个更新\(x\)
    1. \(x\)\(\frac{s}{m + 1}\)概率随机替换\(A\)中的一个元素
    2. \(m ++\)

证明

​ 假定已经流过的数据量为\(n\),采样池大小为\(s\)

​ 考虑最普通的情况,第\(j\)个元素进了采样池,之后再也没有被选出去,那么在第\(n\)个元素流过之后,这个元素还在采样池中的概率是\(\frac{s}{n}\),计算方法很简单,被选进去的概率是\(\frac{s}{j}\),为保证不被选出去,两种情况:新的元素没有选进来,新的元素选进来了但是该元素没有被替换掉。这两种情况对应着\((1 - \frac{s}{j + 1}) + \frac{s}{j + 1}*\frac{s - 1}{s} = \frac{j}{j + 1}\)。依次类推最终可以计算得到结果\(\frac{s}{n}\)

Bloom Filter

问题定义

原问题

​ 给定一个数据集\(U\),从中抽取一个子集\(S\),给定一个数\(q\in U\),判定\(q\in S\)是否成立。

近似问题

​ 给定一个数据集\(U\),从中抽取一个子集\(S\),给定一个数\(q\in U\),如果\(q\in S\)输出\(yes\),否则以至少\(1 - \delta\)概率输出\(no\)

近似哈希的方法

算法

  1. \(H\)是一族通用哈希函数:\([U] \rightarrow [m]\)\(m = \frac{n}{\delta}\)
  2. 随机选择\(h \in H\),并维护数组\(A[m]\)\(S\)的大小是\(n\)
  3. 对每一个\(i \in S\)\(A[h(i)] = 1\)
  4. 给定查询,返回\(yes\)当且仅当\(A[h(i)] = 1\)

证明

​ 如果\(q \in S\),返回的就是\(yes\),如果\(q \notin S\),那么本应该返回\(no\),但是有一定的概率返回\(yes\),这就是错误的情况,元素本来不在\(S\)中,但是它的哈希值却与其中的某个元素的哈希值相同。\(\sum_{j \in S}P[h(q) = h(j)] \leq \frac{n}{m} = \delta\),这样就计算除了\(m\)的值,并解决了近似问题。

Bloom Filter方法

算法

  1. \(H\)是一族独立的理想哈希函数:\([U] \rightarrow [m]\)
  2. 随机选取\(h_1,...,h_d \in H\),并维护数组\(A[m]\)
  3. 对于每一个\(i \in S\)
    1. 对于每一个\(j \in [1,d]\)
      1. \(A[h_j(i)] = 1\)
  4. 给定查询\(q\),返回\(yes\)当且仅当\(\forall j \in [d],A[h_j(q)] = 1\)

证明

​ 与第一个算法的证明基本一致,失败的概率为\(P \leq (\frac{n}{m})^d = \delta\),所以最终的代价就是\(m = O(nlog\frac{1}{\delta})\)

总结

​ 至此,已经介绍完了所有的亚线性空间算法,接下来要进入更加有有趣的亚线性时间算法。敬请期待。