<p>The setting is as follows:</p>

<p>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).</p>

<p>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.</p>

<p>In their <a href="http://ilpubs.stanford.edu:8090/504/1/2001-34.pdf" rel="nofollow">well cited paper</a>, 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.</p>

<p>Their results include:</p>

<ol>
<li>Every exact counting algorithm requires $\Omega(N)$ space.</li>
<li>$(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).</li>
<li>Every $(1+\epsilon)$-multiplicative algorithm requires $\Omega(\epsilon^{-1} \cdot \log^2{(N\epsilon)})$ space.</li>
</ol>

<p>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):</p>

<ol>
<li>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).</li>
<li>Requires only $O(\log(N\epsilon) + \epsilon^{-1})$ space and runs in $O(1)$ time worst case.</li>
</ol>

<p>I'm not familiar with this field, and don't know what changed since 2002, so my questions are:</p>

<p><strong>Has there been work on additive approximation of number of bits in a sliding window?</strong></p>

<p>What is the current state of the art result for this problem?</p>

<p>Are there practical usages that require specifically the multiplicative factor that makes the additive factor not interesting?</p>

CC BY-SA 3.0
2014-06-03T10:16:44.423Z
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
Suresh Venkat
CC BY-SA 3.0
2017-09-14T06:46:13.400Z
Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient summing over sliding windows. Are you one of the authors? ;)
Danny
<ds.algorithms><approximation-algorithms><streaming-algorithms><sliding-window>
Additive error in counting the number of 1's in a sliding window?
R B
# Additive error in counting the number of 1's in a sliding window?

(Asked by: username_0 on 2014-05-19)

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](http://ilpubs.stanford.edu:8090/504/1/2001-34.pdf), 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?

**Tags:** ds.algorithms, approximation-algorithms, streaming-algorithms, sliding-window
> **Comments:**
> **username_1**: 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  
> **username_2**: Ran Ben-Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient summing over sliding windows. Are you one of the authors? ;)  

---

## 0 answers

