www-ai.cs.tu-dortmund.de/LEHRE/FACHPROJEKT/SS12/paper/counting/lee2006.pdf
curblk,
3Again, to simplify notation, we assume that ε2i/16 and 16/ε are integers.
295
position 1 2 3 4 5 6 7 8 9 bit stream f ′
e 1 1 1 1 1 1 1 1 1 sampled 1-bit for λh-block
√ √ √ λh-block 1 2 3
sampled [...] sampled 1-bit in position 1. In level h, we have curblkh = 3, offseth = 2, Qh,e = 〈1, 2, 3〉 and h,e = 2. Then in level h + 1, we set curblkh+1 = 3/2 = 2, offseth+1 = 2, Qh+1,e = 〈1〉 and h+1,e = λh + 2 = 5 [...] counter for x has size O(nx
εn ) where
291
position 1 2 3 4 5 6 7 8 9 10 11 12 bit stream 1 0 1 1 1 1 1 1 1 1 0 0
sampled 1-bit √ √ √
λ-block 1 2 3 4 window W23
position 13 14 15 16 17 18 19 20 21 22 23 …
