<p>As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue.</p>

<p>The setting is as follows: Let $\epsilon&gt;0$. we need to maintain a space-efficient data structure that supports the following operations:</p>

<p>$add(x)$ - add $x$ to the front of the queue. All elements are integers in the range $0,1,\ldots, R$.</p>

<p>$remove()$ - removes the oldest element from the queue. The function is not required to output the element (or anything else).</p>

<p>$sum()$ - returns an approximation for the sum of the elements in the queue. The estimation error must be smaller than $n\cdot R\cdot \epsilon$, where $n$ is the number the queue contains at the moment of the query.</p>

<p><strong>All operations are required to run in constant time.</strong></p>

<hr>

<p>For example, consider $\epsilon = 0.1, R = 100$ and the sequence:</p>

<p>$add(50)$</p>

<p>$add(33)$</p>

<p>$add(72)$</p>

<p>$remove()$</p>

<p>$sum()$</p>

<p>Then the algorithm is required to answer a number within $105\pm 20$.</p>

<hr>

<p>A trivial solution maintains a linked list with a sum variable, computing the exact sum. The space requirements of this algorithm is $O(n\cdot\log R)$.</p>

<p>Another simple solution is to keep a linked list of approximated values (represent each element using $O(\log\frac{1}{\epsilon})$ bits), which results in a $O(n\log\frac{1}{\epsilon})$ space algorithm.</p>

<p>Our solution uses some compression techniques to reduce the complexity to $O(\min\{\frac{1}{\epsilon} + \log n, n\log\left\lceil1+\frac{1}{n\epsilon}\right\rceil\})$ by keeping an approximate representation of "blocks" of elements.</p>

<hr>

<blockquote>
  <p><strong>Is this result known? Are there known sub-linear (in the number of elements in the queue) algorithms for computing statistics (sum / norms / percentiles/ etc.) of a queue?</strong></p>
</blockquote>

<hr>

<p>This problem can be viewed as a generalization of summing over sliding windows in streaming data (e.g., see <a href="http://www-cs.stanford.edu/~datar/papers/sicomp_streams.pdf" rel="nofollow">[1]</a> and <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8399&amp;rep=rep1&amp;type=pdf" rel="nofollow">[2]</a>). </p>

CC BY-SA 3.0
2015-08-26T13:27:35.003Z
Can you present your result as an answer to this question?
jbapple
CC BY-SA 3.0
2015-08-26T13:33:00.327Z
My initial thought was that it might be possible to maintain $k$ simultaneous sliding window estimates on windows of size $1,2,\dots,2^k$, or maybe on windows of size $1, 1+\epsilon, \dots, (1+\epsilon)^k$, but I'd like to hear if this is related to your solution before attempting to dot the 'i's and cross the 't's.
jbapple
CC BY-SA 3.0
2015-08-27T01:32:00.397Z
@jbapple- my solution is different; we call a sequence of arriving elements a "block" and partition the queue into fixed, $O(\frac{1}{\epsilon})$, number of blocks. The length of each block, and the number of bits used for its representation, change as the ratio between $\epsilon$ and $n$ changes.I'm not sure, but I think your solution requires a $O(\log n)$ multiplicative factor, as for $\epsilon=\omega(\log n)$, the leading space factor in a sliding window estimate is $O(\frac{1}{\epsilon})$. Also, running time might be logarithmic, as you need to update all sketches when an element arrives.
R B
CC BY-SA 3.0
2015-08-27T12:24:03.187Z
@RB: no, it's still amortized constant running time I think, because you update the 2^l size window only once each 2^l number.  It can probably even be deamortized so it takes at most constant time, but that's probably irrelevant.
Zsbán Ambrus
<ds.algorithms><space-bounded><data-streams><streaming-algorithms>
Integer queue summation
R B
# Integer queue summation

(Asked by: username_0 on 2015-08-23)

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue.

The setting is as follows: Let $\epsilon>0$. we need to maintain a space-efficient data structure that supports the following operations:

$add(x)$ - add $x$ to the front of the queue. All elements are integers in the range $0,1,\ldots, R$.

$remove()$ - removes the oldest element from the queue. The function is not required to output the element (or anything else).

$sum()$ - returns an approximation for the sum of the elements in the queue. The estimation error must be smaller than $n\cdot R\cdot \epsilon$, where $n$ is the number the queue contains at the moment of the query.

**All operations are required to run in constant time.**

---

For example, consider $\epsilon = 0.1, R = 100$ and the sequence:

$add(50)$

$add(33)$

$add(72)$

$remove()$

$sum()$

Then the algorithm is required to answer a number within $105\pm 20$.

---

A trivial solution maintains a linked list with a sum variable, computing the exact sum. The space requirements of this algorithm is $O(n\cdot\log R)$.

Another simple solution is to keep a linked list of approximated values (represent each element using $O(\log\frac{1}{\epsilon})$ bits), which results in a $O(n\log\frac{1}{\epsilon})$ space algorithm.

Our solution uses some compression techniques to reduce the complexity to $O(\min\{\frac{1}{\epsilon} + \log n, n\log\left\lceil1+\frac{1}{n\epsilon}\right\rceil\})$ by keeping an approximate representation of "blocks" of elements.

---

> **Is this result known? Are there known sub-linear (in the number of elements in the queue) algorithms for computing statistics (sum / norms / percentiles/ etc.) of a queue?**

---

This problem can be viewed as a generalization of summing over sliding windows in streaming data (e.g., see [[1]](http://www-cs.stanford.edu/~datar/papers/sicomp_streams.pdf) and [[2]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8399&rep=rep1&type=pdf)).

**Tags:** ds.algorithms, space-bounded, data-streams, streaming-algorithms

> **Comments:**
> **username_1**: Can you present your result as an answer to this question?  
> **username_1**: My initial thought was that it might be possible to maintain $k$ simultaneous sliding window estimates on windows of size $1,2,\dots,2^k$, or maybe on windows of size $1, 1+\epsilon, \dots, (1+\epsilon)^k$, but I'd like to hear if this is related to your solution before attempting to dot the 'i's and cross the 't's.  
> **username_0**: @username_1- my solution is different; we call a sequence of arriving elements a "block" and partition the queue into fixed, $O(\frac{1}{\epsilon})$, number of blocks. The length of each block, and the number of bits used for its representation, change as the ratio between $\epsilon$ and $n$ changes.I'm not sure, but I think your solution requires a $O(\log n)$ multiplicative factor, as for $\epsilon=\omega(\log n)$, the leading space factor in a sliding window estimate is $O(\frac{1}{\epsilon})$. Also, running time might be logarithmic, as you need to update all sketches when an element arrives.  
> **username_2**: @RB: no, it's still amortized constant running time I think, because you update the 2^l size window only once each 2^l number.  It can probably even be deamortized so it takes at most constant time, but that's probably irrelevant.  

---

## 0 answers

