www-ai.cs.tu-dortmund.de/LEHRE/FACHPROJEKT/SS12/paper/counting/CountSketch.pdf
final_paper.dvi
oni[q]] occur, then |hi[q]si[q]−nq(`)| ≤ 8γ. Hence, for a fixed i,
Pr[|hi[q]si[q] − nq(`)| ≤ 8γ] ≥ 5
8 .
The expected number of such indices i is at least 5t/8. By Chernoff bounds, the number of such indices [...] i [q] ≤
8 ∑m
q′=k+1 n2 q′
b . By the
Markov inequality,
Pr[Small-Variancei[q]] ≥ 1 − 1
8 (1)
Let No-Collisionsi[q] be the event that Ai[q] does not contain any of the top k elements.
If b ≥ 8k,
Pr[No- [...] Pr[No-Collisionsi[q]] ≥ 1 − 1
8 (2)
Let Small-Deviationi[q](`) be the event that
|hi[q]si[q] − nq(`)| 2 ≤ 8Var[hi[q]si[q]].
Then,
Pr[Small-Deviationi[q](`)] ≥ 1 − 1
8 . (3)
By the union bound,
Pr[No-Collisionsi[q] …
