6
$\begingroup$

Consider a stream of elements $s_1s_2\ldots s_N$. A counter-based frequency estimation algorithm uses $m$ counters and is required to answer queries of the form "How many times did $x$ appear"?

It is well known that answering such queries to within a one-sided additive error of $N/(k+1)$ requires at least $k$ counters by any deterministic algorithm (see here).

Assume we allow randomized algorithms for the task.

Which lower bounds (on the number of counters required) can we derive on a randomized algorithm which satisfies $$ f_x -N\epsilon\le\mathbb E(\text{query}(x))\le f_x,$$ where the expectancy is over the algorithm internal randomness?

In particular, the Majority algorithm (see 1 and [2]) is able to find a majority item in the stream using a single counter.

Is there a randomized algorithm which is able to identify, using a single counter, an element arriving at least $N(0.5-c)$ of the time for some fixed $c>0$ (with probability larger than 1/2)?

1] R. Boyer and J. Moore. A Fast Majority Vote Algorithm. Technical Report 1981-32, Institute for Computing Science, University of Texas, Austin, 1981.

2] M. Fischer and S. Salzberg. Finding a Majority Among N Votes: Solution to Problem 81-5. Journal of Algorithms, 3:376–379, 1982.

Improve this question
$\endgroup$
2
  • $\begingroup$ Setting $N = 1/\epsilon$, there is an easy reduction from the Index problem which gives $\Omega(1/\epsilon)$ space complexity. $\endgroup$
    – Sasho Nikolov
    Dec 6, 2015 at 5:25
  • $\begingroup$ Thanks @SashoNikolov. I'm actually interested in the more fine-grained lower bound (i.e. not asymptotically). As in my second question, it's interesting to see if we can find elements appearing less than half of the stream with a single counter. I'm not sure any improvement over deterministic algorithms is possible, all I could come up with was a $0.5N-O(\sqrt N)$ identification using a single counter. $\endgroup$
    – R B
    Dec 6, 2015 at 8:43

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.