网站建设服务费怎么做会计分录,led照明企业网站模板,医疗网站怎么做优化,建站cms1 大数据亚线性空间算法 场景#xff1a;用二进制存储一个数字N#xff0c;需要log(N)的空间 问题#xff1a;如果N特别大而且这样的N又特别的多#xff0c;该怎么办呢#xff1f; 思路#xff1a;减少一些准确性#xff0c;从而节省更多的空间。 解决办法#xff1a;使…1 大数据亚线性空间算法 场景用二进制存储一个数字N需要log(N)的空间 问题如果N特别大而且这样的N又特别的多该怎么办呢 思路减少一些准确性从而节省更多的空间。 解决办法使用近似计数算法每一个数字的存储只需要loglog(N)loglog(N)loglog(N)的空间复杂度就行了。 1.1 流模型的计数问题
问题定义
定义一个数据流ai,i∈[1,m],ai∈[1,n]ai,i∈[1,m],a_i∈[1,n]ai,i∈[1,m],ai∈[1,n]频率向量fii∈[1,n],fi∈[1,m]fii∈[1,n],f_i∈[1,m]fii∈[1,n],fi∈[1,m]。
要求设计空间复杂度为loglog(N)loglog(N)loglog(N)的算法记录其中出现了几个aia_iai
morris算法 将X初始化为0 循环如果aia_iai出现一次就以1/(2X)1/(2^X)1/(2X)的概率将X增加1 返回f^(2X−1)\hat{f}(2^X-1)f^(2X−1)
利用切比雪夫不等式P[∣X−μ∣≥ϵ]⩽σ2/ϵ2P[|X−μ|≥ϵ]⩽σ^2/ϵ^2P[∣X−μ∣≥ϵ]⩽σ2/ϵ2证明
期望E[2XN−1]NE[2^{X_N}−1]NE[2XN−1]N
方差var[2XN−1]12N2−12Nvar[2^{X_N}−1] \frac{1}{2}N^2−\frac{1}{2}Nvar[2XN−1]21N2−21N
令切比雪夫不等式中的XY2XN−1XY2^{X_N}−1XY2XN−1。
最终得到公式 P[∣Y−N∣≥ϵ]⩽N2−N2ϵ2P[|Y−N|≥ϵ]⩽\frac{N^2−N}{2ϵ^2}P[∣Y−N∣≥ϵ]⩽2ϵ2N2−N。
morris算法
运行 k 次 morris 算法记录记录结果(X1,...,Xk)(X_1,...,X_k)(X1,...,Xk)返回γ1k∑i1k(2Xi−1)\gamma\frac{1}{k}\sum^k_{i1}(2^{X_i}-1)γk1∑i1k(2Xi−1)
证明
E[γ]NE[γ]NE[γ]N
D[γ]N2−N2kD[γ]\frac{N^2−N}{2k}D[γ]2kN2−N。
P[∣γ−N∣≥ϵ]⩽N2−N2kϵ2P[|γ−N|≥ϵ]⩽\frac{N^2−N}{2kϵ^2}P[∣γ−N∣≥ϵ]⩽2kϵ2N2−N
morris算法
重复morris算法mO(log(1δ))mO(log(\frac{1}{δ}))mO(log(δ1))次取mmm个结果的中位数
证明
E[Xi]0.9E[X_i]0.9E[Xi]0.9 μ0.9mμ0.9mμ0.9m P[∑Xi0.5m]δP[∑X_i0.5m]δP[∑Xi0.5m]δ
1.2 不重复元素数
问题定义
定义一个数据流ai,i∈[1,m],ai∈[1,n]a_i,i∈[1,m],a_i∈[1,n]ai,i∈[1,m],ai∈[1,n]频率向量fi,i∈[1,n],fi∈[1,m]f_i,i∈[1,n],f_i∈[1,m]fi,i∈[1,n],fi∈[1,m]。计算不等于0并且不重复的元素个数
FM算法 随机选取一个哈希函数[0,1][0,1][0,1]上的均匀分布 h:[n]↦[0,1]h:[n]↦[0,1]h:[n]↦[0,1] z1z1z1 当一个数字 i 出现的时候zmin{z,h(i)}zmin\{z,h(i)\}zmin{z,h(i)} 返回1z−1\frac{1}{z}-1z1−1
证明
期望E[z]1d1E[z]\frac{1}{d1}E[z]d11
var[z]⩽2(d1)(d2)2(d1)(d1)var[z]⩽\frac{2}{(d1)(d2)}\frac{2}{(d1)(d1)}var[z]⩽(d1)(d2)2(d1)(d1)2
P[∣z−1d1∣ϵ1d1]var[z]ϵd122ϵ2P[|z−\frac{1}{d1}|ϵ\frac{1}{d1}]\frac{var[z]}{\frac{ϵ}{d1}^2}\frac{2}{ϵ^2}P[∣z−d11∣ϵd11]d1ϵ2var[z]ϵ22
FM算法
总共运行 q 次FM算法为每一次的运行随机选取一个哈希函数 hj:[n]↦[0,1]h_j:[n]↦[0,1]hj:[n]↦[0,1]初始化zj1z_j1zj1开始计数每当 i 出现更新zjmin(zj,hj(i))z_jmin(z_j,h_j(i))zjmin(zj,hj(i))Z1q∑j1qzjZ\frac{1}{q}∑_{j1}^qz_jZq1∑j1qzj返回1Z−1\frac{1}{Z}-1Z1−1
证明
E[Z]1d1E[Z]\frac{1}{d1}E[Z]d11
var[Z]⩽2(d1)(d2)1q2(d1)(d1)1qvar[Z]⩽\frac{2}{(d1)(d2)}\frac{1}{q}\frac{2}{(d1)(d1)}\frac{1}{q}var[Z]⩽(d1)(d2)2q1(d1)(d1)2q1
P[∣X−d∣ϵ′d]2q(2ϵ′1)2P[|X−d|ϵd]\frac{2}{q}(\frac{2}{ϵ}1)^2P[∣X−d∣ϵ′d]q2(ϵ′21)2
计算代价缩小为O(1ϵ2log1δ)O(\frac{1}{ {\epsilon}^2}log\frac{1}{\delta})O(ϵ21logδ1) FM′算法
随机选取一个哈希函数 h:[n]↦[0,1]h:[n]↦[0,1]h:[n]↦[0,1](z1,z2,...,zk)1(z_1,z_2,...,z_k)1(z1,z2,...,zk)1也就是所有的z的初值都设置为1维护当前看到的最小的k个哈希值返回kzk\frac{k}{z_k}zkk
证明
P[∣kzk−d∣ϵd]P[k(1ϵ)dzk]P[k(1−ϵ)dzk]P[|\frac{k}{z_k}−d|ϵd]P[\frac{k}{(1ϵ)d}z_k]P[\frac{k}{(1−ϵ)d}z_k]P[∣zkk−d∣ϵd]P[(1ϵ)dkzk]P[(1−ϵ)dkzk]
P2ϵ2kP \frac{2}{ {\epsilon}^2k}Pϵ2k2
PracticalFM算法 和 BJKST算法的准备知识
若我们无法存储实数则采用PracticalFM算法 和 BJKST算法 若∀j1,...,jk∈[b],∀j1,...,jk∈[a],p[h(i1)j1∧...∧h(ik)jk]1bk则:一个从[a]映射到[b]的哈希函数是k−wise的若\forall j_{1},...,j_{k} \in [b], \forall j_{1},...,j_{k} \in [a],\\ p[h(i_{1}) j_{1} \wedge ...\wedge h(i_{k}) j_{k}] \frac{1}{b^k}\\ 则:一个从[a]映射到[b]的哈希函数是k-wise的 若∀j1,...,jk∈[b],∀j1,...,jk∈[a],p[h(i1)j1∧...∧h(ik)jk]bk1则:一个从[a]映射到[b]的哈希函数是k−wise的
zeros(h(j))max(i:p%2i0)也就是展开成二进制后末尾0的个数比如8对应的二进制是1000则zeros(8)3。zeros(h(j)) max(i:p \% 2^{i} 0)\\ 也就是展开成二进制后末尾0的个数\\ 比如8对应的二进制是1000则zeros(8) 3。 zeros(h(j))max(i:p%2i0)也就是展开成二进制后末尾0的个数比如8对应的二进制是1000则zeros(8)3。
PracticalFM算法 从2−wiseindependent2-wise\ independent2−wise independent哈希函数族中随机选取 h:[n]↦[n]h:[n]↦[n]h:[n]↦[n] z0z0z0 如果zeros(h(j))zzeros(h(j))zzeros(h(j))z zzeros(h(j))zzeros(h(j))zzeros(h(j)) 返回d^2z12\hat{d}2^{z\frac{1}{2}}d^2z21
算法解释
1−22C1 - \frac{2\sqrt{2} }{C}1−C22概率满足d/C≤d^≤Cdd / C \leq \hat{d} \leq Cdd/C≤d^≤Cd。
证明
E[Yr]d2rE[Y_{r}] \frac{d}{2 ^ r}E[Yr]2rd
var[Yr]≤d2rvar[Y_{r}] \leq \frac{d}{2^r}var[Yr]≤2rd。
最终正确的概率应该大于1−22C1 - \frac{2\sqrt{2} }{C}1−C22。
BJKST算法 随机选择2−wiseindependent2-wise~ independent2−wise independent哈希函数 h:[n]→[n]h:[n]→[n]h:[n]→[n] 随机选择2−wiseindependent2-wise~independent2−wise independent哈希函数 g:[n]→[bϵ−4log2n]g:[n]→[bϵ−4log2n]g:[n]→[bϵ−4log2n] z0,B∅z0,B∅z0,B∅ 若zeros(h(j))zzeros(h(j))zzeros(h(j))z BB∪(g(j),zeros(h(j)))BB∪(g(j),zeros(h(j)))BB∪(g(j),zeros(h(j)))若∣B∣cϵ2|B| \frac{c}{\epsilon^2}∣B∣ϵ2c zz1zz1zz1从B中删除(α,β)(α,β)(α,β)其中βzβzβz return d^∣B∣2z\hat{d}|B|2^zd^∣B∣2z
算法解释
要想清楚地解释这个算法只需要清楚两点即可。
当出现的一个新的元素时 如果zeros(h(j))zzeros(h(j))zzeros(h(j))z 则将相应的二元组插入到B中如果B中的元素数量超过了某个大小 z的值相应的就增加1就将其中第二项小于z的元素从中删除。
证明
该算法可以实现至少2/3概率保证(1ϵ)近似。
E[Yr]d2rE[Y_{r}] \frac{d}{2 ^ r}E[Yr]2rd
var[Yr]≤d2rvar[Y_{r}] \leq \frac{d}{2^r}var[Yr]≤2rd
最终P[FAIL]1/6P[FAIL]1/6P[FAIL]1/6。
再加上之前出去算法假设造成的错误概率最终总的错误概率在1/3之内。
评价
空间复杂度为O(logn1ϵ2(log1ϵloglogn))O(logn \frac{1}{\epsilon ^ 2}(log\frac{1}{\epsilon} loglogn))O(lognϵ21(logϵ1loglogn))。
1.3 点查询
问题定义
定义一个数据流aii∈[1,m],ai∈[1,n]aii∈[1,m],a_i∈[1,n]aii∈[1,m],ai∈[1,n]频率向量fi,i∈[1,n],fi∈[1,m]fi,i∈[1,n],f_i∈[1,m]fi,i∈[1,n],fi∈[1,m]。计算流中所有的元素出现次数
知识准备
范数lp∥x∥p(∑i∣xi∣p)1pl_{p} \left \| x \right \|_{p} {(\sum_{i}{|x_{i}|^p})}^{\frac{1}{p} }lp∥x∥p(∑i∣xi∣p)p1lpl_plp点查询频度估计 给定数据流σσσ和aia_iai输出fi^\hat{f_i}fi^满足fi^fi±ϵ∣∣f∣∣p\hat{f_{i} } f_{i} \pm \epsilon \left|| \textbf{f} \right||_{p}fi^fi±ϵ∣∣f∣∣p ∣∣x∣∣1≥∣∣x∣∣2≥...≥∣∣x∣∣∞\left|| x \right||_{1} \geq \left|| x \right||_{2} \geq ... \geq \left|| x \right||_{\infty}∣∣x∣∣1≥∣∣x∣∣2≥...≥∣∣x∣∣∞p越大估计越准确 ‖x‖0‖x‖_0‖x‖0是不同元素的数目 ‖x‖1‖x‖_1‖x‖1是流的长度 ‖x‖∞‖x‖_∞‖x‖∞是最大频度
Misra_Gries算法
维护一个集合A其中的元素是(i,fi^)(i,\hat{f_{i} })(i,fi^) A←∅A←∅A←∅ 对每一个数据流中的元素e if e∈A令(e,fe^)→(e,fe^1)(e,\hat{f_{e} }) \rightarrow (e,\hat{f_{e} } 1)(e,fe^)→(e,fe^1) else if ∣A∣1ϵ|A| \frac{1}{\epsilon}∣A∣ϵ1将(e,1)插入A else 将所有A中计数减 1if fj^0\hat{f_{j} } 0fj^0从A中删除(j,0) 对于查询 i如果i∈Ai∈Ai∈A返回fi^\hat{f_{i} }fi^否则返回 0
证明
对任意的查询 i返回 fi^\hat{f_{i} }fi^ 满足fi−ϵm≤fi^≤fif_{i} - \epsilon m \leq \hat{f_{i} } \leq f_{i}fi−ϵm≤fi^≤fi。
证明
结合算法过程总共有两种情况。
如果不发生减1的情况那么fi^fi\hat{f_{i} } f_{i}fi^fi 如果发生了减1的情况有fi^fi\hat{f_{i} } f_{i}fi^fi 假设发生了c次减1的情况总数减少cϵ≤m\frac{c}{\epsilon} \leq mϵc≤m每个计数至多减少cfi^≥fi−c≥fi−ϵm\hat{f_{i} } \geq f_{i} - c \geq f_{i} - \epsilon mfi^≥fi−c≥fi−ϵm。
算法的空间代价是O(ϵ−1logn)O(\epsilon^{-1}logn)O(ϵ−1logn)
Metwally算法
维护一个集合A集合中的元素是(i,fi^)(i,\hat{f_i})(i,fi^)
A←∅对每一个数据流中的元素e if e∈A令(e,fi^)←(e,fi^1)(e,\hat{f_i})←(e,\hat{f_i}1)(e,fi^)←(e,fi^1)else if ∣A∣1ϵ|A| \frac{1}{\epsilon}∣A∣ϵ1将(e,1)插入Aelse 将(e,MIN1)插入A并删除一个满足fe^MIN\hat{f_{e} } MINfe^MIN 查询 i如果i∈Ai∈Ai∈A返回fi^\hat{f_i}fi^否则返回MIN
证明的目标
对任意的查询 i返回fi≤fi^≤fiϵmf_{i} \leq \hat{f_{i} } \leq f_{i} \epsilon mfi≤fi^≤fiϵm
证明
① 如果不发生删除的情况那么fi^fi\hat{f_{i} } f_{i}fi^fi。
② 如果删除计数一定不大于删除后的MIN有fi^≥fi\hat{f_{i} } \geq f_{i}fi^≥fiA中元素总是mMIN1ϵ≤m⇒MIN≤ϵmMIN \frac{1}{\epsilon} \leq m \Rightarrow MIN \leq \epsilon mMINϵ1≤m⇒MIN≤ϵm每个元素至多超出真实值MINfi^≤fiϵm\hat{f_{i} } \leq f_{i} \epsilon mfi^≤fiϵm。
算法的空间代价是O(ϵ−1logn)O(\epsilon^{-1}logn)O(ϵ−1logn) 新的定义
Sketch
定义在数据流σ上的数据结构DS(σ)是一个Sketch
如果存在一个Space−Efficient的合并算法COMB使得COMB(DS(σ1),DS(σ2))DS(σ1∘σ2)COMB(DS(\sigma_{1}),DS(\sigma_{2})) DS(\sigma_{1} \circ \sigma_{2})COMB(DS(σ1),DS(σ2))DS(σ1∘σ2)其中∘是数据流的连接操作。
Linear Sketch
定义在[n]上的数据流σ上的sketching输出sk(σ)如果sk(σ)取值为维度ll(n)的向量并且是f(σ)的线性函数那么sk(σ)是一个Linear Sketchl是这个sketch的维度。
Count-Min算法 C[1...t][1...k]←0,k2ϵ,t⌈log1δ⌉C[1...t][1...k] \leftarrow \textbf{0},k \frac{2}{\epsilon},t \left \lceil log\frac{1}{\delta} \right \rceilC[1...t][1...k]←0,kϵ2,t⌈logδ1⌉ 随机选择 t 个2−wise独立哈希函数 hi:[n]→[k]h_i:[n]→[k]hi:[n]→[k] 对每一个出现的更新(j,c)进行如下操作 for i1 to t C[i][hi(j)]C[i][hi(j)]cC[i][h_{i}(j)] C[i][h_{i}(j)] cC[i][hi(j)]C[i][hi(j)]c 针对对于a的查询返回 fa^min1≤i≤tC[i][hi(a)]\hat{f_{a} } \min_{1 \leq i \leq t}{C[i][h_{i}(a)]}fa^min1≤i≤tC[i][hi(a)]
算法解释
在算法开始时构造一个 t 行 k 列 的空数组可以认为每一行是独立的算法在运行时同时记录了t个这样的数组。在每出现一个流数据的时候对每一个数组进行一次更新注意元素的第二个下标用的是数据的哈希值。
算法在运行的过程中可能产生冲突也就是两个不同的流数据的哈希值可能相同这个时候就会导致结果偏大但是因为有相当于t次的重复计算通过取最小值的方法来进行一些弥补
证明
该算法以1−δ概率给出l1l_{1}l1点查询问题的(1ϵ)近似
评价
算法的空间代价为O(1ϵlog1δ(lognlogm))O(\frac{1}{\epsilon}log\frac{1}{\delta}(logn logm))O(ϵ1logδ1(lognlogm))
Count-Median算法 C[1...t][1...k]←0,k2ϵ,t⌈log1δ⌉C[1...t][1...k] \leftarrow \textbf{0},k \frac{2}{\epsilon},t \left \lceil log\frac{1}{\delta} \right \rceilC[1...t][1...k]←0,kϵ2,t⌈logδ1⌉ 随机选择t个2−wise独立哈希函数hi:[n]→[k]h_i:[n]→[k]hi:[n]→[k] 对每一个出现的更新(j,c)进行如下操作 for i1 to t C[i][hi(j)]C[i][hi(j)]cC[i][h_{i}(j)] C[i][h_{i}(j)] cC[i][hi(j)]C[i][hi(j)]c 针对对于a的查询令∣C[x][hx(a)]∣median1≤i≤t∣C[i][hi(a)]∣|C[x][h_x(a)]| median_{1 \leq i \leq t}{|C[i][h_{i}(a)]|}∣C[x][hx(a)]∣median1≤i≤t∣C[i][hi(a)]∣ 返回fa^∣C[x][hx(a)]∣\hat{f_a} |C[x][h_x(a)]|fa^∣C[x][hx(a)]∣
算法解释
与Count−MinSketch算法的计数方法完全一致差别就在返回值的获取上返回的是所有t个数组值的绝对值的中位数对应的原始值。
Count Sketch算法 C[1...k]←0,k3ϵ2C[1...k] \leftarrow 0,k \frac{3}{\epsilon^2}C[1...k]←0,kϵ23 随机选择1个2−wise独立哈希函数h:[n]→[k]h:[n]→[k]h:[n]→[k] 随机选择1个2−wise独立哈希函数g:[n]→−1,1g:[n]→{−1,1}g:[n]→−1,1 对于每一个更新(j,c) C[h(j)]C[h(j)]c∗g(j)C[h(j)] C[h(j)] c * g(j)C[h(j)]C[h(j)]c∗g(j) 针对查询a返回f^g(a)∗C[h(j)]\hat{f} g(a) * C[h(j)]f^g(a)∗C[h(j)]
Count Sketch算法 C[1...t][1...k]←0,k3ϵ2,tO(log1δ)C[1...t][1...k] \leftarrow \textbf{0},k \frac{3}{\epsilon^2},t O(log\frac{1}{\delta})C[1...t][1...k]←0,kϵ23,tO(logδ1) 随机选择1个2−wise独立哈希函数 hi:[n]→[k]h_i:[n]→[k]hi:[n]→[k] 随机选择1个2−wise独立哈希函数 gi:[n]→{−1,1}g_i:[n] \rightarrow \{-1,1\}gi:[n]→{−1,1} 对于每一个更新(j,c) 对于i:1→ti:1→ti:1→t C[hi(j)]C[hi(j)]c∗gi(j)C[h_i(j)] C[h_i(j)] c * g_i(j)C[hi(j)]C[hi(j)]c∗gi(j) 返回f^median1≤i≤tgi(a)C[i][hi(a)]\hat fmedian~1≤i≤tgi(a)C[i][h_i(a)]f^median 1≤i≤tgi(a)C[i][hi(a)]
算法解释
相当于是将Count Sketch算法运行了t次最后取了中值。利用齐尔诺夫不等式可以解决令Xi1⇔第i次运行成功成功概率是2/3最后只要成功的个数超过一半即可。最终是通过t控制了δ。 1.4 频度矩估计
Basic AMS算法
(m,r,a)←(0,0,0)(m,r,a)←(0,0,0)(m,r,a)←(0,0,0)对于每一个更新 j m←m1m←m1m←m1β←randombitwithP[β1]1mβ ← random~bit ~with~ P[β 1] \frac{1}{m}β←random bit with P[β1]m1if β1 ajr0if ja r←r1r←r1r←r1 返回Xm(rk−(r−1)k)X m(r^k - (r - 1)^k)Xm(rk−(r−1)k)
算法分析
E[X]FkE[X] F_kE[X]Fk
Var[X]≤kn1−1kFk2Var[X] \leq kn^{1 - \frac{1}{k} }F_k^2Var[X]≤kn1−k1Fk2
利用切比雪夫不等式对结果进行检验P[∣X−E[x]∣ϵE[X]]kn1−1kϵ2P[|X - E[x]| \epsilon E[X]]\frac{kn^{1 - \frac{1}{k} } }{\epsilon^2}P[∣X−E[x]∣ϵE[X]]ϵ2kn1−k1
评价
存储 m 和 r 需要 log n 位 存储 a 需要 log m 位 算法的方差太大需要进一步的改进但是其相应的存储代价为O(logmlogn)O(logmlogn)O(logmlogn)
Final AMS 算法
利用Median‑of‑Mean技术调用Basic AMS算法;计算tclog1δt clog\frac{1}{\delta}tclogδ1个平均值每个平均值是r3kϵ2n1−1kr \frac{3k}{\epsilon ^ 2}n^{1 - \frac{1}{k} }rϵ23kn1−k1次调用的平均值返回t个数值的中间值
证明
记{Xij}i∈[t],j∈[r]\{X_{ij}\}_{i \in [t],j \in [r]}{Xij}i∈[t],j∈[r]是与X独立同部分的随机变量集合。
Yi1r∑j1rXijY_i \frac{1}{r}\sum_{j 1}^{r}X_{ij}Yir1∑j1rXij
Z∑i1tYiZ \sum_{i 1}^{t}Y_iZ∑i1tYi
计算E[Yi]E[X],Var[Yi]Var[X]kE[Y_i] E[X],Var[Y_i] \frac{Var[X]}{k}E[Yi]E[X],Var[Yi]kVar[X]
根据切比雪夫不等式有P[∣Yi−E[Yi]∣≥ϵE[Yi]]≤Var[X]kϵ2E[X]2P[|Y_i - E[Y_i]| \geq \epsilon E[Y_i]] \leq \frac{Var[X]}{k\epsilon^2E[X]^2}P[∣Yi−E[Yi]∣≥ϵE[Yi]]≤kϵ2E[X]2Var[X]
取值r3Var[X]kϵ2E[X]2r \frac{3Var[X]}{k\epsilon^2E[X]^2}rkϵ2E[X]23Var[X]将期望和方差带入可以计算得到算法中给出的结果
现在P[∣Yi−E[Yi]∣≥ϵE[Yi]]≤13P[|Y_i - E[Y_i]| \geq \epsilon E[Y_i]] \leq \frac{1}{3}P[∣Yi−E[Yi]∣≥ϵE[Yi]]≤31
最后利用Median技术进行处理即可。
评价
算法的空间代价为O(1ϵ2log1δkn1−1k(logmlogn))O(\frac{1}{\epsilon^2}log\frac{1}{\delta}kn^{1 - \frac{1}{k} }(logm logn))O(ϵ21logδ1kn1−k1(logmlogn))当k≥2时代价过大。
Basic F2 AMS 算法 随机选择4−wise独立的哈希函数 h:[n]→−1,1h:[n]→{−1,1}h:[n]→−1,1 x←0 对于每一个更新(j,c) x←xc∗h(j)x \leftarrow x c * h(j)x←xc∗h(j) 返回x2x^2x2
分析
这个算法本身并没有什么比较好的效果但是用过median−of−mean技术的优化可以得到一个(ϵ,δ)的算法。所以在这里的证明中只计算出结果的期望和方差就行了。
证明
记Yjh(j),j∈[1,n],X∑j1nfjYjY_j h(j),j \in [1,n],X \sum_{j 1}^{n}f_jY_jYjh(j),j∈[1,n],X∑j1nfjYj
E[X2]∑i1nfiYi×∑j1nfjYjE[X^2] \sum_{i 1}^{n}f_iY_i \times \sum_{j 1}^{n}f_jY_jE[X2]∑i1nfiYi×∑j1nfjYj
Var[X2]E[X4]−E[X2]2Var[X^2] E[X^4] - E[X^2]^2Var[X2]E[X4]−E[X2]2
评价
算法的空间代价是O(logmlogn)下面先使用mean将犯错概率限制在1/3再使用median技术对结果进行优化。
1.5 固定大小采样
水库抽样算法
m←0使用数据流的前s个元素对抽样数组进行初始化 A[1,...,s],m←sA[1,...,s],m\leftarrow sA[1,...,s],m←s对于每一个更新x x以sm1\frac{s}{m 1}m1s概率随机替换A中的一个元素m
证明
假定已经流过的数据量为n采样池大小为s
考虑最普通的情况第j个元素进了采样池之后再也没有被选出去那么在第n个元素流过之后这个元素还在采样池中的概率是s/n
计算方法被选进去的概率是s/j为保证不被选出去两种情况新的元素没有选进来新的元素选进来了但是该元素没有被替换掉。这两种情况对应着(1−sj1)sj1∗s−1sjj1(1 - \frac{s}{j 1}) \frac{s}{j 1}*\frac{s - 1}{s} \frac{j}{j 1}(1−j1s)j1s∗ss−1j1j。依次类推最终可以计算得到结果s/n。
1.6 Bloom Filter
给定一个数据集U从中抽取一个子集S给定一个数q∈U判定q∈S是否成立。
近似哈希的方法
令H是一族通用哈希函数[U]→[m]mnδ[U]→[m]m \frac{n}{\delta}[U]→[m]mδn随机选择 h∈H并维护数组A[m]S的大小是n对每一个 i∈SA[h(i)]1A[h(i)]1A[h(i)]1给定查询q返回yes当且仅当A[h(i)]1A[h(i)]1A[h(i)]1
证明
如果q∈S返回的就是yes如果q∉S那么本应该返回no但是有一定的概率返回yes这就是错误的情况元素本来不在S中但是它的哈希值却与其中的某个元素的哈希值相同。∑j∈SP[h(q)h(j)]≤nmδ\sum_{j \in S}P[h(q) h(j)] \leq \frac{n}{m} \delta∑j∈SP[h(q)h(j)]≤mnδ这样就计算除了m的值并解决了近似问题。
Bloom Filter方法 令H是一族独立的理想哈希函数[U]→[m] 随机选取h1,...,hd∈Hh_1,...,h_d \in Hh1,...,hd∈H并维护数组A[m] 对于每一个i∈S 对于每一个j∈[1,d] A[hj(i)]1A[h_j(i)] 1A[hj(i)]1 给定查询q返回yes当且仅当∀j∈[d],A[hj(q)]1\forall j \in [d],A[h_j(q)] 1∀j∈[d],A[hj(q)]1
证明
失败的概率为P≤(nm)dδP \leq (\frac{n}{m})^d \deltaP≤(mn)dδ所以最终的代价就是mO(nlog1δ)m O(nlog\frac{1}{\delta})mO(nlogδ1)
2 大数据亚线性时间算法
2.1 计算图的平均度算法Vertex Cover一
定义
已知G(V,E)G(V,E)G(V,E) 求平均度dˉ∑u∈Vd(u)n\bar{d} \frac{\sum_{u\in V}d(u)}{n}dˉn∑u∈Vd(u) 假设G是简单图没有平行边和自环
分析
将具有相似或者相同度数的节点分组然后估算每个分组的平均度数。
首先将所有的点进行分桶分成t个桶第i个桶里的点集合为Bi{v∣(1β)(i−1)d(v)(1β)i},0i≤t−1B_i\{v|(1\beta)^{(i-1)} d(v) (1\beta)^{i}\},0i\leq t-1Bi{v∣(1β)(i−1)d(v)(1β)i},0i≤t−1其中β是超参数。
于是BiB_iBi中的点的总度数有上下界如公式所示(1β)(i−1)∣Bi∣d(Bi)(1β)i∣Bi∣(1\beta)^{(i-1)}|B_i| d(B_i) (1\beta)^{i}|B_i|(1β)(i−1)∣Bi∣d(Bi)(1β)i∣Bi∣
进一步的G的总度数可以表示为∑i0t−1(1β)(i−1)∣Bi∣∑u∈Vd(u)∑i0t−1(1β)i∣Bi∣\sum_{i0}^{t-1}(1\beta)^{(i-1)}|B_i| \sum_{u\in V}d(u) \sum_{i0}^{t-1}(1\beta)^{i}|B_i|∑i0t−1(1β)(i−1)∣Bi∣∑u∈Vd(u)∑i0t−1(1β)i∣Bi∣
于是我们可以得到∑i0t−1(1β)(i−1)∣Bi∣ndˉ∑i0t−1(1β)i∣Bi∣n\frac{\sum_{i0}^{t-1}(1\beta)^{(i-1)}|B_i|}{n} \bar{d} \frac{\sum_{i0}^{t-1}(1\beta)^{i}|B_i|}{n}n∑i0t−1(1β)(i−1)∣Bi∣dˉn∑i0t−1(1β)i∣Bi∣
于是将问题转化成了对Bin\frac{B_i}{n}nBi的估计
算法
从V取出样本集合SSi←S∩BiS_i \gets S \cap B_iSi←S∩Biρi←SiS\rho_i \gets \frac{S_i}{S}ρi←SSi返回 dˉ^∑i0t−1ρi(1β)i\hat{\bar{d} } \sum_{i0}^{t-1}\rho_i(1\beta)^{i}dˉ^∑i0t−1ρi(1β)i
算法的思想其实很简单将Bin\frac{B_i}{n}nBi理解为一种概率就是随机选一个点这个点属于Bi的概率这样理解算法就很简单了。
评价
算法的思想和计算都很简单只是进行了一个非常巧妙的转化但是这个算法仍然是有问题的
2.2 计算图的平均度算法二
改进算法
对于较小的桶的ρi\rho_iρi假定一个dˉ\bar{d}dˉ的一个下阶α\alphaα。
从V中抽取样本SSi←S∩BiS_i \gets S \cap B_iSi←S∩Bifori∈{0,…,t−1}do\boldsymbol{for}\ i \in \{0,\dots,t-1\}\ \boldsymbol{do}for i∈{0,…,t−1} do if∣Si∣≥θρthen\boldsymbol{if}\ |S_i| \geq \theta_\rho\ \boldsymbol{then}if ∣Si∣≥θρ thenρi←∣Si∣∣S∣\rho_i \gets \frac{|S_i|}{|S|}ρi←∣S∣∣Si∣else\boldsymbol{else}else ρi←0\rho_i\gets 0ρi←0 returndˉ^∑i0t−1ρi(1β)i\boldsymbol{return}\ \hat{\bar{d} } \sum_{i0}^{t-1}\rho_i(1\beta)^{i}return dˉ^∑i0t−1ρi(1β)i
我们将算法的结果调整为以2/3的概率有(0.5−ϵ)dˉdˉ^(1ϵ)dˉ(0.5-\epsilon)\bar{d} \hat{\bar{d} } (1 \epsilon)\bar{d}(0.5−ϵ)dˉdˉ^(1ϵ)dˉ。
这里给出一组参数使得能够满足上述结果
βϵ4\beta \frac{\epsilon}{4}β4ϵ∣S∣Θ(nα⋅poly(logn,1/ϵ))|S| \Theta(\sqrt{\frac{n}{\alpha} }\cdot poly(log\ n,1/\epsilon))∣S∣Θ(αn⋅poly(log n,1/ϵ))t⌈log(1β)n⌉1t \left \lceil log_{(1\beta)}n \right \rceil 1t⌈log(1β)n⌉1θρ1t38⋅ϵαn∣S∣\theta_{\rho} \frac{1}{t}\sqrt{\frac{3}{8}\cdot\frac{\epsilon\alpha}{n} }|S|θρt183⋅nϵα∣S∣
2.3 计算图的平均度算法三
算法改进的思想
我们将算法出现的误差归结到边上让我们来看看究竟是哪些边导致了这样的错误。将节点分为U,V/U两部分其中U是度数较小的节点V/U是度数较大的节点E(U,V/U)表示连接两个集合的边的集合。于是我们断言出现误差就是因为E(U,V/U)中的边我们只计算了一次关于这一点我们回忆一下之前举的例子就很好理解了。于是我们只要找到每次抽样的时候这部分的边的比例就可以了。
改进算法
利用E[Δi]E[\Delta_i]E[Δi]的1ϵ1\epsilon1ϵ估计可以得到Δiρi(1β)i\Delta_i\rho_i(1\beta)^iΔiρi(1β)i是Tin的(1ϵ)(1β)\frac{T_i}{n}的(1\epsilon)(1\beta)nTi的(1ϵ)(1β)估计。于是乎经过改造的算法如下所示
从V中抽取样本S∣S∣O~(Lρϵ2),Lpoly(lognϵ),ρ1tϵ4⋅αn|S| \tilde{O}(\frac{L}{\rho\epsilon^2}),Lpoly(\frac{log\ n}{\epsilon}),\rho \frac{1}{t}\sqrt{\frac{\epsilon}{4}\cdot \frac{\alpha}{n} }∣S∣O~(ρϵ2L),Lpoly(ϵlog n),ρt14ϵ⋅nαSi←S∩BiS_i \gets S \cap B_iSi←S∩Bifori∈{0,…,t−1}do\boldsymbol{for}\ i \in \{0,\dots,t-1\}\ \boldsymbol{do}for i∈{0,…,t−1} do if∣Si∣≥θρthen\boldsymbol{if}\ |S_i| \geq \theta_\rho\ \boldsymbol{then}if ∣Si∣≥θρ then ρi←∣Si∣∣S∣\rho_i \gets \frac{|S_i|}{|S|}ρi←∣S∣∣Si∣estimateΔiestimate\ \Delta_iestimate Δi else\boldsymbol{else}else ρi←0\rho_i\gets 0ρi←0 returndˉ^∑i0t−1(1Δi)ρi(1β)i\boldsymbol{return}\ \hat{\bar{d} } \sum_{i0}^{t-1}(1\Delta_i)\rho_i(1\beta)^{i}return dˉ^∑i0t−1(1Δi)ρi(1β)i
2.4 计算图的平均度算法四
Alg III
利用E[Δi]E[\Delta_i]E[Δi]的1ϵ1\epsilon1ϵ估计可以得到Δiρi(1β)i\Delta_i\rho_i(1\beta)^iΔiρi(1β)i是Tin的(1ϵ)(1β)\frac{T_i}{n}的(1\epsilon)(1\beta)nTi的(1ϵ)(1β)估计。于是乎经过改造的算法如下所示
从V中抽取样本S∣S∣O~(Lρϵ2),Lpoly(lognϵ),ρ1tϵ4⋅αn|S| \tilde{O}(\frac{L}{\rho\epsilon^2}),Lpoly(\frac{log\ n}{\epsilon}),\rho \frac{1}{t}\sqrt{\frac{\epsilon}{4}\cdot \frac{\alpha}{n} }∣S∣O~(ρϵ2L),Lpoly(ϵlog n),ρt14ϵ⋅nαSi←S∩BiS_i \gets S \cap B_iSi←S∩Bifori∈{0,…,t−1}do\boldsymbol{for}\ i \in \{0,\dots,t-1\}\ \boldsymbol{do}for i∈{0,…,t−1} do if∣Si∣≥θρthen\boldsymbol{if}\ |S_i| \geq \theta_\rho\ \boldsymbol{then}if ∣Si∣≥θρ then ρi←∣Si∣∣S∣\rho_i \gets \frac{|S_i|}{|S|}ρi←∣S∣∣Si∣estimateΔiestimate\ \Delta_iestimate Δi else\boldsymbol{else}else ρi←0\rho_i\gets 0ρi←0 returndˉ^∑i0t−1(1Δi)ρi(1β)i\boldsymbol{return}\ \hat{\bar{d} } \sum_{i0}^{t-1}(1\Delta_i)\rho_i(1\beta)^{i}return dˉ^∑i0t−1(1Δi)ρi(1β)i
Alg IV
α←n\alpha \gets nα←ndˉ^−∞\hat{\bar{d} } -\inftydˉ^−∞whiledˉ^αdo\boldsymbol{while}\ \hat{\bar{d} } \alpha\ \boldsymbol{do}while dˉ^α do α←α/2\alpha \gets \alpha/2α←α/2ifα1nthen\boldsymbol{if}\ \alpha \frac{1}{n}\ \boldsymbol{then}if αn1 then return0;\boldsymbol{return}\ 0;return 0; dˉ^←AlgIII∼α\hat{\bar{d} } \gets AlgIII_{\sim \alpha}dˉ^←AlgIII∼α returndˉ^\boldsymbol{return}\ \hat{\bar{d} }return dˉ^
算法相关指标
近似比(1ϵ)(1 \epsilon)(1ϵ)
运行时间O~(n)⋅poly(ϵ−1logn)n/dˉ\tilde{O}(\sqrt{n})\cdot poly(\epsilon^{-1}log\ n)\sqrt{n/\bar{d} }O~(n)⋅poly(ϵ−1log n)n/dˉ
2.5 近似最小支撑树
定义
已知G(V,E),ϵ,ddeg(G)G(V,E),ϵ,ddeg(G)G(V,E),ϵ,ddeg(G)边(u,v)的权重是wuv∈{1,2,…,w}∪{∞}w_{uv}∈\{1,2,…,w\}∪\{∞\}wuv∈{1,2,…,w}∪{∞}
求M^\hat{M}M^满足(1−ϵ)M≤M^≤(1ϵ)M(1−ϵ)M≤\hat{M}≤(1ϵ)M(1−ϵ)M≤M^≤(1ϵ)M令M为minTspansGW(T)min_{TspansG}{W(T)}minTspansGW(T)
分析
定义
G的子图G(i)(V,E(i))G^{(i)}(V,E^{(i)})G(i)(V,E(i)) E(i){(u,v)∣wuv≤i}E(i)\{(u,v)|w_{uv}≤i\}E(i){(u,v)∣wuv≤i} 连通分量的个数为C(i)
定理若M为所有这样的子图的连通分量的数目的和Mn−w∑i1w−1C(i)Mn-w\sum_{i1}^{w-1}{C^{(i)} }Mn−w∑i1w−1C(i)
证明设图G的一个最小生成树为MST(V,E′)MST(V,E)MST(V,E′)MST的子图MST(i)(V′,E′(i)),V′V,E′(i){(u,v)∣(u,v)∈E(i)(u,v)∈E′}MST^{(i)} (V,E^{(i)}),VV,E^{(i)}\{(u,v)|(u,v) \in E^{(i)} \And (u,v) \in E\}MST(i)(V′,E′(i)),V′V,E′(i){(u,v)∣(u,v)∈E(i)(u,v)∈E′} 设αiα_iαi为MST 中权重为i的边的数目 ∑i1αi\sum_{i1}{\alpha_i}∑i1αi表示MST中所有边权大于1的边的个数这个数值加1应该就是在MST中将这些边从MST中去掉之后得到的MST(l)MST^{(l)}MST(l)中的连通分量的个数 MST(l)MST^{(l)}MST(l)的连通分量的个数应该与G(i)是一致的于是我们得到了下面的式子∑i1αiC(l)−1\sum_{i1}{\alpha_i}C^{(l)}-1∑i1αiC(l)−1。 于是我们就可以用如下的方法计算M了 M∑i1wi⋅αi∑i1wαi∑i2wαi⋯∑iwwαiC(0)−1C(1)−1⋯C(w−1)−1n−1C(1)−1⋯C(w−1)−1n−w∑i1w−1C(i)\begin{align*} M \sum_{i1}^{w}{i \cdot \alpha_i}\sum_{i1}^{w}{\alpha_i} \sum_{i2}^{w}{\alpha_i} \dots \sum_{iw}^{w}{\alpha_i}\\ C^{(0)}-1 C^{(1)}-1 \dots C^{(w-1)}-1\\ n-1C^{(1)}-1 \dots C^{(w-1)}-1\\ n-w\sum_{i1}^{w-1}{C^{(i)} } \end{align*} Mi1∑wi⋅αii1∑wαii2∑wαi⋯iw∑wαiC(0)−1C(1)−1⋯C(w−1)−1n−1C(1)−1⋯C(w−1)−1n−wi1∑w−1C(i)
时间复杂度
运行w次求解连通分量个数的时间复杂度w⋅O(d/ϵ3)O(dw4/ϵ′3)w\cdot O(d/\epsilon^3)O(dw^4/\epsilon^3)w⋅O(d/ϵ3)O(dw4/ϵ′3)。
2.6 求点集合的直径
定义
已知有m个点点与点之间的距离使用邻接矩阵表示则Dij表示点i到点j的距离D是一个对称矩阵并且满足三角不等式Dij≤DikDkjD_{ij} \leq D_{ik} D_{kj}Dij≤DikDkj。
求出点对(i,j)使得Dij是最大的则Dij是这m个点的集合的直径。
求解算法The Indyk’s Algorithm
任选k∈[1,m]k∈[1,m]k∈[1,m]选出lll使得∀i,Dki≤Dkl\forall i,D_{ki} \leq D_{kl}∀i,Dki≤Dkl返回(k,l),Dkl(k,l),D_{kl}(k,l),Dkl
算法分析之近似比分析
最优解记为 opt是点 i 和点 j 之间的距离
则有opt2≤Dkl≤opt\frac{opt}{2} \leq D_{kl} \leq opt2opt≤Dkl≤opt
算法分析之近似比证明不等式
关于不等式的右侧易证左侧的证明如下所示 optDij≤DikDkj≤DklDkl≤2Dkl\begin{align*} opt D_{ij}\\ \leq D_{ik} D_{kj}\\ \leq D_{kl} D_{kl}\\ \leq 2D_{kl} \end{align*} opt≤≤≤DijDikDkjDklDkl2Dkl
算法评价
算法的时间复杂度为O(m)O(n)O(m) O(\sqrt{n})O(m)O(n)。
2.7 求连通分量的数目
定义
已知G(V,E),ϵ,ddeg(G)G (V,E),\epsilon,d deg(G)G(V,E),ϵ,ddeg(G)图G用邻接表表示其中d表示所有节点中度最大的节点的度∣V∣n,∣E∣m≤d⋅n|V| n,|E| m \leq d\cdot n∣V∣n,∣E∣m≤d⋅n
求出一个y使得C−ϵ⋅n≤y≤Cϵ⋅nC - \epsilon \cdot n \leq y \leq C \epsilon \cdot nC−ϵ⋅n≤y≤Cϵ⋅n其中C为使用线性算法求解得到的标准解
问题分析
记顶点v所属的连通分量中的节点数目为nvn_vnvA∈V是一个连通分量的点集合则存在如下等式关系∑u∈A1nu∑u∈A1∣A∣1\sum_{u \in A}{\frac{1}{n_u} } \sum_{u \in A}{\frac{1}{|A|} } 1∑u∈Anu1∑u∈A∣A∣11这个很容易证明因为同一个连通分量中的每一个点的nvn_vnv是一样的都是分量中点的个数的倒数。如此则最终的结果C可以表示为∑u∈V1nu\sum_{u\in V}{\frac{1}{n_u} }∑u∈Vnu1。因此进一步地对C的估计可以转化为对1nu\frac{1}{n_u}nu1的估计。
求解问题的思想
nun_unu很大精确计算很难但是此时1nu\frac{1}{n_u}nu1很小可以用一个很小的常量代替1nu\frac{1}{n_u}nu1(0或者ϵ2\frac{\epsilon}{2}2ϵ)如果我设nu^min{nu,2ϵ}\hat{n_u} min\{n_u,\frac{2}{\epsilon}\}nu^min{nu,ϵ2}则C^∑u∈V1nu^\hat{C} \sum_{u \in V}{\frac{1}{\hat{n_u} } }C^∑u∈Vnu^1使用C^\hat{C}C^来估计C可以获得很不错的结果。
算法-计算nu^\hat{n_u}nu^
思想很简单就是一个小型的搜索如果搜索到的点的个数小于2ϵ\frac{2}{\epsilon}ϵ2就继续搜索否则直接返回2ϵ\frac{2}{\epsilon}ϵ2。
时间复杂度为O(d⋅1ϵ)O(d\cdot \frac{1}{\epsilon})O(d⋅ϵ1)d越大用的时间越长1ϵ\frac{1}{\epsilon}ϵ1越大用的时间越长。
算法-计算nun_unu
从节点集合中随机选出rb/ϵ2r b/{\epsilon}^2rb/ϵ2个节点构成节点U对每个节点应用上一个算法于是最终的C^nr∑u∈U1nu^\hat{C} \frac{n}{r} \sum_{u \in U}{\frac{1}{\hat{n_u} } }C^rn∑u∈Unu^1时间复杂度为O(d/ϵ3)O(d/{\epsilon}^3)O(d/ϵ3)
3 并行计算算法
3.1 基本问题一
MapReduce
使用MR模型进行计算有几个要点
计算分轮次进行每一轮的输入和输出的数据都是形如key,value的每一轮分为Map、Shuffle、ReduceMap每个数据被map函数处理输出一个新的数据集合也就是改变了key,valueShuffle对编程人员透明所有在Map中输出的数据被按照key分组具备相同key 的数据被分配到相同的reducerReduce输入k,v1,v2,…输出新的数据集合针对这样的计算框架我们的设计目标为更少的轮数、更少的内存、更大的并行度
问题实例
下面我们来看一些具体的问题实例这些例子都是可以并行的当然实现的逻辑不止一种有多种可能性这里只是给出一种方法。
构建倒排索引
定义给定一组文档统计每一个单词出现在哪些文件中
Map函数docID,content→word,docIDdocID,content \rightarrow word,docIDdocID,content→word,docID在map函数处理的时候对content进行拆分并将分出来的word都转换成word加上对应的docID输出。Reduce函数word,docID→word,listofdocIDword,docID \rightarrow word,list\ of\ docIDword,docID→word,list of docIDmap函数结束之后shuffle会自动将key相同的键值对输出到一个机器上我们直接对这个批次中的数据规整到一起即可。
单词计数
定义 给定一组文档统计每一个单词出现的次数
Map函数docID,content→word,1Reduce函数word,1→word,count
检索
定义给定行号和相应的文档内容统计指定单词出现的位置*行号
Map函数略Reduce函数略
3.2 基本问题二
简介
问题实例矩阵乘法
就是简单的矩阵乘法我们知道普通的矩阵乘法的时间复杂度是O(m⋅n⋅d)对于一个m⋅d和d⋅n的矩阵相乘。通过并行计算框架我们极大加速这个过程的执行具体的两个方法如下面所示
矩阵乘法1
定义矩阵A和矩阵B(A,i,j)指向矩阵A的第i行j列的元素但并不是真实的这个元素而是表示一种索引aij表示的则是这个元素。
Map ((A,i,j),aij)→(j,(A,i,aij))((B,j,k),bjk)→(j,(B,k,bjk)) Reduce(j,(A,i,aij)),(j,(B,k,bjk))→((i,k),aij∗bjk)MapnothingidentityReduce((i,k),(v1,v2,…))→((i,k),∑vi)
思路剖析目标矩阵上的每个元素都是由d个中间元素aij∗bjk累加得到的我们先统把这样的所有的元素求出来然后累加起来即可。对于目标矩阵上的每个元素都是如此。
矩阵乘法2 Map函数 ((A,i,j),aij)→((i,x),(A,j,aij)) for all x∈[1,n]((B,j,k),bjk)→((y,k),(B,j,bjk)) for all y∈[1,m] Reduce函数((i,k),(A,j,aij))∧((i,k),(B,j,bjk))→((i,k),∑aij∗bjk)
思路剖析相对于第一个方法方法2先不把中间元素求出来而是把求解每个目标矩阵上要用到的2d个基本元素都放到一起然后进行点积操作。
3.3 排序算法
问题简介
算法
使用p台处理器输入i,A[i]i,A[i]i,A[i] Mapi,A[i]→j,((i,A[i]),y)i,A[i] \rightarrow j,((i,A[i]),y)i,A[i]→j,((i,A[i]),y) 输出i%p,((i,A[i]),0)i\%p,((i,A[i]),0)i%p,((i,A[i]),0) 以概率T/n为所有j∈[0,p−1]j ∈ [0, p − 1]j∈[0,p−1]输出j,((i,A[i]),1)j,((i,A[i]),1)j,((i,A[i]),1) 否则输出j,((i,A[i]),0)j,((i,A[i]),0)j,((i,A[i]),0) Reduce 将y1的数据收集为S并排序构造(s1,s2,...,sp−1)(s_1,s_2,...,s_{p−1})(s1,s2,...,sp−1)sks_ksk为S中第k⌈∣S∣p⌉k\left \lceil \frac{|S|}{p} \right \rceilk⌈p∣S∣⌉将y0的数据收集为D(i,x)∈D满足skx≤sk1s_k x \leq s_{k1}skx≤sk1输出k,(i,x) Mapnothingidentity Reduce$ j, ((i, A[i]), . . . )$ 将所有(i,A[i])(i, A[i])(i,A[i])根据$ A[i]$排序并输出
思路剖析整体的思路就是先对整个数据进行一个划分分成不同的小段段与段之间的数据具有严格的大小关系这样每个段内部的数据都是一些很接近的数据如此我们就可以借助一些高效的排序手段对每个段内部的数据集进行排序。然后**解决问题的一个关键就是我们对数据的划分的好坏这一点我们可以通过理论来证明有很大概率可以保证划分的效果。**但是也不绝对出现某个计算节点上基本没有数据而另一个计算节点上出现超量的数据也是有可能的当然这是极小概率事件。
3.4 计算最小支撑树生成树
问题简介
已知图G(V,E)其中V,E分别是图的点集合和边集合。图G的一个子图T∗(V,E′)T^*(V,E)T∗(V,E′)被称为最小生成树当且仅当T∗T^∗T∗是连通的并且∑(u,v)∈T∗w(u,v)minT{∑(u,v)∈Tw(u,v)}\sum_{(u,v)\in T^*}{w(u,v)} \min_{T}\{\sum_{(u,v)\in T}{w(u,v)}\}∑(u,v)∈T∗w(u,v)minT{∑(u,v)∈Tw(u,v)}。
在小数据范围内通常使用Kruskal或Prim算法求解当图的规模变得较大时由于这两个算法的复杂度的限制在有限时间内将无法求解。这时可以借助MapReduce来加速计算。
算法主要思想
利用图划分算法将图G划分成k个子图在每个子图中计算最小生成树具体如下。
将节点分成k部分对每一个(i,j)∈[k]2(i,j)\in [k]^2(i,j)∈[k]2令Gij(Vi∪Vj,Eij)G_{ij} (V_i\cup V_j,E_{ij})Gij(Vi∪Vj,Eij)为节点Vi∪VjV_i\cup V_jVi∪Vj上的导出子图在每个Gij上分别求解MijMSF(Gij)M_{ij}MSF(G_{ij})MijMSF(Gij)令H∪i,jMijH \cup_{i,j}M_{ij}H∪i,jMij计算MMST(H)MMST(H)MMST(H)
注MSF指的是最小生成森林举个例子来说明这个概念在一个最小生成树中有n−1条边可以理解为是一个只有一棵树的最小生成森林。同理在同一个图中也存在有两棵树、三棵树的最小生成森林只要这个森林是min{∑(u,v)∈Forestw(u,v)}\min\{\sum_{(u,v)\in Forest}w(u,v)\}min{∑(u,v)∈Forestw(u,v)}就可以。
本质上讲算法的本质就是先在局部算好生成树然后用剩余的连接这些生成树的边组成一个新的图并求出这个新的图的最小生成树作为最总的结果。
MR算法
Mapinput:(u,v),NULL 转化(h(u),h(v));(u,v)针对上述转化数据如果h(u)h(v)则对所有j∈[1,k]输出(h(u),j);(u,v) Reduceinput:(i,j);Eij 令MijMSF(Gij)对Mij中的每条边e(u,v)输出NULL;(u,v) MapnothingidentityReduceMMST(H)
其中h是哈希函数可以用一个取值均匀的随机算法实现ps用随机算法生成哈希表而不是每次运行都随机取值。
当然在划分时还要考虑各个计算节点的负载均衡问题。
4 外存模型算法
4.1 外存模型
外存模型
到目前为止按照存储模型我们学过的算法模型应该分为两种一种是RAM模型也就是我们常用的算法的设计模型另一种是I/O模型内存比数据量小外存是无限的。
外存访问与内存访问有一些差异
与外存相比内存的速度更快外存的连续访问比随机访问代价小也就是说以块(block)为单位访问
基于外存模型的基本问题
在I/O模型中内存的大小为M页面大小为B外存大小无限页面大小为B。
连续读取外存上的N个数据需要O(N/B)次I/O
如何计算矩阵乘法
输入两个大小为N×N的矩阵X和Y
将矩阵分为大小为M/2×M/2\sqrt{M}/2\times\sqrt{M}/2M/2×M/2的块考虑X×Y矩阵中的每个块显然共有O((NM)2)O((\frac{N}{\sqrt{M} })^2)O((MN)2)个块需要输出每个块需要扫描NM\frac{N}{\sqrt{M} }MN对输入块每次内存计算需要O(M/B)次I/O共计O((NM)3⋅M/B)O((\frac{N}{\sqrt{M} })^3\cdot M/B)O((MN)3⋅M/B)次I/O
链表
进行三种操作insert(x,p),remove§,traverse(p,k)
内存模型下各个操作的时间复杂度updateO(1)traverseO(k)
在外存模型下将一个链表中连续的元素放在一个大小为B的块中。同时令每个块大小至少为B/2
remove删除后如果小于B/2与邻接的块合并合并后如果大于B则平均划分insert插入后如果大于B则平均划分traverseO(2k/B)
搜索结构
进行三种操作insert(x),remove(x),query(x)
(a,b)−tree:2≤a≤(b1)/2(a,b)-tree:2\leq a \leq (b1)/2(a,b)−tree:2≤a≤(b1)/2
类似二分查找树⇒(p0,k1,...,kc,pc)\Rightarrow (p_0,k_1,...,k_c,p_c)⇒(p0,k1,...,kc,pc)
root节点有0个或者≥2个孩子除了root每个非叶子节点的孩子数目∈[a,b]
remove找到对应叶子节点删除后如果小于a与邻接的块合并合并后如果大于b平均划分进而在上一层递归删除节点或者调整键值insert找到对应叶子节点插入后如果大于b平均划分递归向上一层插入query:O(loga(N/a))query:O(log_a(N/a))query:O(loga(N/a))
4.2 外存排序
外存排序问题
考虑外存排序算法的时候要与外存模型紧密地结合起来。
算法
给定N个数据将其分成大小为O(M)的组每一组数据可以在内存排序将每一组数据从外存读进来需要O(M/B)次I/O对所有分组进行以上操作于是每个分组内部都是已经排好序的数据对这些排好序的分组进行多路归并排序每次可以归并O(M/B)个分组
过程解释
首先需要明白的一点是从外存向内存转移数据的时候一次只能转移B的数据量。于是要想一次把内存读慢相应的I/O次数就是O(M/B)。另外进行多路归并排序时至多可以归并多少分组。从每个分组读出来一个页面然后进行排序所以这里跟每个分组的大小没有关系只跟内存的大小有关所以是O(M/B)。
图示 评价
时间复杂度分为两个部分一个是分组内排序另一个是分组间归并排序。
对于分组内排序只需要将每个分组的数据读入内存即可这部分对应的时间复杂度为O(N/B)O(N/B)O(N/B)。对于归并排序相应的时间代价应该是每一趟归并的开销之和而每一趟归并都需要把所有数据都导入到内存中一次这个时间代价为O(N/B)O(N/B)O(N/B)。而归并的趟数可以表示为O(logM/BNB)O(log_{M/B}\frac{N}{B})O(logM/BBN)。综上所述总的时间开销为O(N/B⋅logM/BNB)O(N/B \cdot log_{M/B}\frac{N}{B})O(N/B⋅logM/BBN)
4.3 List Ranking
List Ranking
定义
[List Ranking Problem]给定大小为N的邻接链表LL存储在数组连续的外存空间中计算每个节点的rank在链表中的序号。
[General List Ranking Problem]给定大小为N的邻接链表LL存储在数组连续的外存空间中L中的每个节点v上存储权重wvw_vwv计算每个节点v的rank从头节点到v的权重和
分析
如果合并链表上的子序列为一个节点也就是页面内部合并将一个页面当作一个节点将权重和做为该节点的权重不影响前后节点的rank 值。如果链表大小至多为M那么利用O(M/B)次I/O可解决这个问题也就是将所有的数据都读入内存使用内存算法解决这个问题。
我们通过一个图片来看一下对这个问题的直观理解如下图所示相关数据为N10,B2,M4。最坏的情况下访问代价为O(N)次I/O 。 算法
输入大小为N的外存链表L
寻找L中的一个顶点独立集 X将X中的节点“跳过”构建新的、更小的外存链表L′递归地求解L′将X中的节点“回填”根据L′的rank构建L的rank
第1.1.4步骤都可以在O(sort)O(NBlogMBNB)O(sort) O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })O(sort)O(BNlogBMBN)次I/O求解则构建如下递归方程
T(N)T((1−α)N)O(NBlogMBNB)T(N) T((1-\alpha)N) O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })T(N)T((1−α)N)O(BNlogBMBN)解方程得T(N)O(NBlogMBNB)T(N) O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })T(N)O(BNlogBMBN)
step~1
按照节点的ID顺序分为forward(f)链表和backward(b)链表将f链表按照red,blue间隔染色将b链表按照green,blue间隔染色。注意这里的f链表和b链表指的是链表的一个连续段该段内的数据的ID顺序关系要么全部与内存中的位置一致要么正好相反。显然一个链表中有多个f链表和b链表。
这一步的实现只需要进行一个外存排序即可实现因此时间代价为O(NBlogMBNB)O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })O(BNlogBMBN)。
step~2,4
L~copy(L)\tilde{L} copy(L)L~copy(L)将链表L按照后继节点的地址排序排序的同时进行如下操作 在step~2将后继节点属于X的节点指针和权重重写在step~4将后继节点属于X的节点指针和权重重写将属于X的节点权重重写 存使用内存算法解决这个问题。
我们通过一个图片来看一下对这个问题的直观理解如下图所示相关数据为N10,B2,M4。最坏的情况下访问代价为O(N)次I/O 。 算法
输入大小为N的外存链表L
寻找L中的一个顶点独立集 X将X中的节点“跳过”构建新的、更小的外存链表L′递归地求解L′将X中的节点“回填”根据L′的rank构建L的rank
第1.1.4步骤都可以在O(sort)O(NBlogMBNB)O(sort) O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })O(sort)O(BNlogBMBN)次I/O求解则构建如下递归方程
T(N)T((1−α)N)O(NBlogMBNB)T(N) T((1-\alpha)N) O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })T(N)T((1−α)N)O(BNlogBMBN)解方程得T(N)O(NBlogMBNB)T(N) O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })T(N)O(BNlogBMBN)
step~1
按照节点的ID顺序分为forward(f)链表和backward(b)链表将f链表按照red,blue间隔染色将b链表按照green,blue间隔染色。注意这里的f链表和b链表指的是链表的一个连续段该段内的数据的ID顺序关系要么全部与内存中的位置一致要么正好相反。显然一个链表中有多个f链表和b链表。
这一步的实现只需要进行一个外存排序即可实现因此时间代价为O(NBlogMBNB)O(\frac{N}{B}log_{\frac{M}{B} }{\frac{N}{B} })O(BNlogBMBN)。
step~2,4
L~copy(L)\tilde{L} copy(L)L~copy(L)将链表L按照后继节点的地址排序排序的同时进行如下操作 在step~2将后继节点属于X的节点指针和权重重写在step~4将后继节点属于X的节点指针和权重重写将属于X的节点权重重写 将L重新按照地址排序
