Алгоритмы обработки потоковых данных, осень 2014: Лекция 4. Алгоритмы подсчета различных элементов

  • Published on
    14-Dec-2014

  • View
    74

  • Download
    10

Embed Size (px)

DESCRIPTION

. 2- -. . -- (AMS'99). $\delta$. $O(\log \frac{1}{\delta} \log n)$ . BJKST'04 $\epsilon$ $\delta$. $O(\log \frac{1}{\delta} \log n)$. $O(\log n + \log \frac{1}{\delta} (\log \frac{1}{\epsilon} + \log \log n))$. , , (1999) BJKST (2004)

Transcript

<ul><li> 1. CS , 2014 19 </li> <li> 2. I (..) X. P I E [ X ] = i2Dom(X) i Pr [ X = i ]. I .. X1; X2; ; Xn 1; ; n E [ P i i Xi ] = P i i E [ Xi ] I D[ X ] = E h (X E [ X ])2 i = E X2 E [ X ]2. I D[ X ] = 2D[ X ]. </li> <li> 3. I .. X Y , 8a; b 2 R Pr [ X = a ^ Y = b ] = Pr [ X = a ] Pr [ Y = b ] : I C.. X Y E [ XY ] = E [ X ] E [ Y ], D[ X + Y ] = D[ X ] + D[ Y ]. I .. X1; ;Xn 2-, 1 i6= j n Xi Xj . I X1;X2; X3 2 f0; 1g, X1 + X2 + X3 = 0 mod 2. I 2- C.. D[ P i Xi ] = P i D[ Xi ]. </li> <li> 4. I Pr [ A _ B ] Pr [ A ] + Pr [ B ]. I Pr [ A ^ B ] Pr [ A ]. .. X 0 a &gt; 0 Pr [ X a ] E [ X ] a : </li> <li> 5. .. X E [ X ] = Pr [ jX j " ] D[ X ] "2 : .. X1;X2; ; Xn , Xi 2 f0; 1g E [ Xi ] = , " &gt; 0 Pr " </li> <li> 6. 1 n X i Xi </li> <li> 7. " # exp(c n): </li> <li> 8. - I H = fhigti =1, hi : K ! V. H 2- -, k16= k2 v1; v2 Pr h U(H) [ h(k1) = v1 ^ h(k2) = v2 ] = 1 jVj2 : I hi : Fp ! Fp. ha;b(x) = a x + b. Pr h U(H) [ a k1 + b = v1 ^ a k2 + b = v2 ] = 1 p2 : a k1 + b = v1; a k2 + b = v2: </li> <li> 9. I = ha1; ; ami, ai 2 [n] = [2l ]. I f [x] = #fi j ai = xg . I d = #fx j f [x] &gt; 0g . I . d. I FM'83 AMS'99: Pr ans 2 [ d 3 ; 3d] 1 . O(log 1 log n). I BJKST'04: Pr [ jans dj "d ] 1 O(log 1 (log n + 1 "2 (log 1 " + log log n))). </li> <li> 10. AMS I zero(p) = maxfi j p 2ig. I : 1. init(): z = 0, h : [n] ! [n] 2- . 2. process(y) : z = max(z, zero(h(y))). 3. answer(): 2z+1 2 . I d . d . Pr d 3 d 0:47: Pr d 1 3d 0:47: </li> <li> 11. AMS. I Xj ;r = [zero(h(j)) r ]. E [ Xj ;r ] = 1 2r ; D[ Xj ;r ] 1 2r : I Yr = P j jf [j ]&gt;0 Xj ;r . E [ Yr ] = d 2r ; D[ Yr ] d 2r : I Pr [ Yr &gt; 0 ] = Pr [ Yr 1 ] E [ Yr ] =1 = d 2r . I Pr [ Yr = 0 ] Pr jYr d 2r j d 2r D[ Yr ] (d=2r )2 2r d . </li> <li> 12. AMS. I a , 3 d 2a+1 2 . Pr [ Ya &gt; 0 ] d 2a p 2 3 . I b , 2b+1 2 1 3 d. Pr [ Yb+1 = 0 ] 2b+1 d p 2 3 . </li> <li> 13. I , , p &lt; 1 2 . I k . I Ti = [ i- ]. I E [ Ti ] p. I , . I Pr h </li> <li> 14. 1 k P i Ti E [ Ti ] </li> <li> 15. 1 2 p i exp(c k). ) I log( 2 2 . I Pr [ ] Pr [ ] + Pr [ ] </li> <li> 16. BJKST. init (): B = [] z = 0 pick 2-ind h : [n] -&gt; [n] process (y): zy = zero (h(y)) i f zy &gt;= z: B c / (eps * eps )): z++ remove a l l (a, b) from B s.t. b &lt; z ans = |B| * pow(2, z) </li> <li> 17. BJKST. I jBj = Yz . I E [ jBj ] = E [ Yz ] = d 2z : I D[ jBj ] = D[ Yz ] d 2z : I z = 0 . I jjBj 2z dj " d , </li> <li> 18. jBj d 2z </li> <li> 19. " d 2z </li> <li> 20. BJKST. "2 d I s , 12 2s 24 "2 . I Pr </li> <li> 21. jBj d 2z </li> <li> 22. " d 2z = Plog n i=1 Pr </li> <li> 23. jBj d 2z </li> <li> 24. " d 2z ^ z = i Ps1 i=1 Pr </li> <li> 25. jBj d 2z </li> <li> 26. " d 2z + Plog n i=s Pr [ z = i ] 1 6 I Pr </li> <li> 27. jBj d 2i </li> <li> 28. " d 2i D[ jBj ] ("d=2i )2 d 2i 1 "2 2i d 2 = 1 "2 2i d . I Ps1 i=1 Pr </li> <li> 29. jBj d 2z </li> <li> 30. " d 2z 1 "2 2s d 1 12 . I Plog n i=s Pr [ z = i ] = Pr Ys1 c "2 d 2s1 "2 "2 "2 c 242 c 48 c . </li> <li> 31. BJKST. "2 log 1 I O( 1 log n). I : B</li></ul>