The setting is as follows:
We're given a stream of bits. At time $t$ you get to see bit $b_t$, and required to output $\widehat{s_t} \approx \Sigma_{i=0}^{N}b_{t-i}$ (i.e. approximately how many 1's appeared in the last $N$ bits).
This can easily be done in $O(1)$ time if $O(N)$ memory is allowed, but the interesting case is when only $m \ll N$ memory is allowed.
In their well cited paper, Datar et al. have given an algorithm for approximate counting of the number of 1's in a sliding window, computed over a stream of bits.
Their results include:
- Every exact counting algorithm requires $\Omega(N)$ space.
- $(1+\epsilon)$-multiplicative algorithm that requires $O(\epsilon^{-1} \cdot \log N \cdot \log {(N\epsilon)})$ space and runs in amortized $O(1)$ time ($O(\log N)$ worst case).
- Every $(1+\epsilon)$-multiplicative algorithm requires $\Omega(\epsilon^{-1} \cdot \log^2{(N\epsilon)})$ space.
Now I think that if we relax the approximation requirement we can do much better - I have a simple algorithm which seems to (unless I'm missing something):
- Gives a $N\cdot \epsilon$-additive factor approximation (i.e. $s_t - N\cdot \epsilon\leq \widehat{s_t} \leq s_t + N\cdot \epsilon$). (Notice that this result is weaker than the multiplicative approximation).
- Requires only $O(\log(N\epsilon) + \epsilon^{-1})$ space and runs in $O(1)$ time worst case.
I'm not familiar with this field, and don't know what changed since 2002, so my questions are:
Has there been work on additive approximation of number of bits in a sliding window?
What is the current state of the art result for this problem?
Are there practical usages that require specifically the multiplicative factor that makes the additive factor not interesting?
