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]).

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you present your result as an answer to this question? $\endgroup$
    – jbapple
    Aug 26, 2015 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, 2015 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, 2015 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, 2015 at 12:24

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.