www-ai.cs.tu-dortmund.de/LEHRE/FACHPROJEKT/SS12/paper/counting/Arasu2004.pdf
(εigNig + k
i=1
εiNi)/N (1)
= (Nig + k · εW
2(2L + 2) )/N (2)
≤ (Nig + εW
2 )/N (3)
≤ ( εW
2 +
εW
2 )/N (4)
≤ εW
N (5)
Equation 3 follows from the fact that k ≤ (2L + 2), and Equation 4 from the fact that Nig [...] shown formally
in Lemma 4.) Therefore, for ` < L, we can construct a
Level−3
Level−2
Level−1
Level−0
Level−0
Level−1
Level−2
Level−3
k2
k+1 2
Figure 2: Construction of C2k+1,ε(m, 2k) from C2k,ε(m, 2k)
sketch [...] Computation of various statistics over the current contents of the window is an important operation [3, 9, 14, 17]. For many statistics, computing an exact answer requires the storage of the entire current …