9
$\begingroup$

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:

  1. Every exact counting algorithm requires $\Omega(N)$ space.
  2. $(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).
  3. 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):

  1. 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).
  2. 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?

$\endgroup$
  • 1
    $\begingroup$ To answer your last question, I'd imagine that sparse inputs (the number of 1s is much less than N) would require a multiplicative approximation rather than additive. Think of an infrequently firing neuronal spike for example $\endgroup$ – Suresh Venkat Jun 3 '14 at 10:16
  • $\begingroup$ Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient summing over sliding windows. Are you one of the authors? ;) $\endgroup$ – Danny Sep 14 '17 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.