2
$\begingroup$

First of all, I am not sure whether this is a research level question. Please let me know if it is not.

The question is about streaming algorithms for the sum of the given data stream. From literature, it is common to consider the questions related to the frequency vector, say, $\vec{m}$, and one has standard algorithms to approximate the p-norm of such a vector. However, a very natural question is, is it possible to approximate the sum of the stream. More formally, suppose we have a frequency vector $\vec{m}$ for the "value vector" $\vec{a}$, i.e., each $a_i$ appears $m_i$ times in the stream, the sum is $\sum a_i\cdot m_i$. (Of course, we assume each $a_i$ is within some interval $I$, as otherwise the question might not be very interesting.)

I noticed that Braverman has papers regarding approximate $\sum_i G(m_i)$ for reasonably general function $G$, but here, with different index $i$, $G$ varies. Hence it is not clear to me how to apply.

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ Say $a_i \in [m]$ and $i \in [n]$. You can trivially just keep a single sum variable and add to it each $a_i$ as it appears, for an $O(\log(m + \log n)$ bit exact solution, which is easily seen to be optimal. Morris's approximate counting algorithm gives a constant factor approximation to the sum in $O(\log \log m + \log \log n)$ bits: algo.inria.fr/flajolet/Publications/Flajolet85c.pdf $\endgroup$
    – Sasho Nikolov
    Apr 27, 2016 at 20:06

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.

Browse other questions tagged or ask your own question.