7
$\begingroup$

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] and [2]).

$\endgroup$
  • $\begingroup$ Can you present your result as an answer to this question? $\endgroup$ – jbapple Aug 26 '15 at 13:27
  • $\begingroup$ 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. $\endgroup$ – jbapple Aug 26 '15 at 13:33
  • $\begingroup$ @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. $\endgroup$ – R B Aug 27 '15 at 1:32
  • $\begingroup$ @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. $\endgroup$ – Zsbán Ambrus Aug 27 '15 at 12:24

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.