<p>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"?</p>

<p>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 (<a href="https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf">see here</a>).</p>

<p>Assume we allow randomized algorithms for the task.</p>

<blockquote>
  <p><strong>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?</strong></p>
</blockquote>

<hr>

<p>In particular, the Majority algorithm (see <a href="https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf">1</a> and [2]) is able to find a majority item in the stream using a single counter. </p>

<blockquote>
  <p><strong>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&gt;0$ (with probability larger than 1/2)?</strong></p>
</blockquote>

<hr>

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

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

CC BY-SA 3.0
2015-12-06T05:25:30.647Z
Setting $N = 1/\epsilon$, there is an easy reduction from the Index problem which gives $\Omega(1/\epsilon)$ space complexity.
Sasho Nikolov
CC BY-SA 3.0
2015-12-06T08:43:15.183Z
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.
R B
<ds.algorithms><lower-bounds><data-streams><streaming-algorithms>
Lower bounds for randomized frequency estimation algorithms
R B
# Lower bounds for randomized frequency estimation algorithms

(Asked by: username_0 on 2015-12-04)

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](https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf)).

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](https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf) 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.

**Tags:** ds.algorithms, lower-bounds, data-streams, streaming-algorithms
> **Comments:**
> **username_1**: Setting $N = 1/\epsilon$, there is an easy reduction from the Index problem which gives $\Omega(1/\epsilon)$ space complexity.  
> **username_0**: 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.  

---

## 0 answers

