Loading...
Please wait, while we are loading the content...
Similar Documents
L12 --heavy Hitters in Streams [jeff Phillips -utah -data Mining] Streaming Algorithms
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | Stream : A = ai in [n] size log n Compute f(A) in poly(log m, log n) space "one pass" Let f_j = |{a_i in A | a_i = j}| F_1 = sum_j f_j = m == total count Goal: Find all j s.t. f_j > phi m phi = 1/k = eps f_j-eps*m <= hat{f}_j <= f_j Misra-Greis [1985] f_j <= hat{f}_j <= f_j + eps*m Count-Min [Cormode + Muthukrishnan '05] How good w/ O(log m + log n) (one counter c + one location l)? ... ########################### c = 0, l = X for (a_i \in A) if (a_i = l) c += 1 else c-= 1 if (c <= 0) c = 1, l = a_i return l ########################### Analysis: if f_j > m/2, then if (l != j) then c decremented at most < m/2 times, but c > m/2 if (l == j) can be decremented < m/2, but is incremented > m/2 if f_j < m/2 for all j, then any answer ok. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.utah.edu/~jeffp/teaching/cs5955/L12-Heavy-Hitters-N.pdf |
| Alternate Webpage(s) | http://www2.cs.utah.edu/~jeffp/teaching/cs5955/L12-Heavy-Hitters-N.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
