# Heavy hitters problem linear scan and auxiliary space

I'm looking at Lecture #2 from this Stanford course http://web.stanford.edu/class/cs168/index.html, let me introduce the HH problem:

We have an array of $n$ elements and we want to know which elements appear at least $\frac{n}{k}$ times, for a given $k$. You can think of $n$ as being pretty large and $k$ small.

Proposition There's no algorithm that solves the Heavy Hitters problem in one pass while using a sublinear amount of space.

An intuition for why this holds is given in the notes:

• for $k=\frac{n}{2}$ we're looking at elements that appear at least twice in the array.
• suppose the array is of the form $x_1, x_2, \ldots , x_{n-1}, y$ , say $S=\{x_i \mid 1\leq i\leq n\}$, then basically the HH problem reduces to a membership problem, is $y\in S$?
• we can solve this problem by saving $S$ as a hash table, and the idea is that we can't solve all the memebership problems (for say $n/2$ elements) using sublinear space.

They suggest using the PHP but I don't see how that applies in this context, any idea?

I can see why the statement is true but I'm looking for a formal proof of it.

• What statement, exactly, are you looking for a proof of? The proposition? One of the three bullets? – David Richerby May 4 '16 at 17:06

Here is the idea, taking as an example the case $k = n/2$ which you mention. Also, let's assume that a word is $\log n$ bits, and that each element consists of $C$ words. In total there are $n^C$ possible elements, forming the universe $U$.

Suppose that an algorithm uses $m$ words of space. For each subset $S$ of $U$ of size $n-1$, let $T(S)$ denote the contents of memory after the algorithm has read the first the elements of $S$ in order. We claim that $T(S_1) \neq T(S_2)$ if $S_1 \neq S_2$. Indeed, suppose without loss of generality that $S_1$ isn't a subset of $S_2$, and let $x \in S_1 \setminus S_2$. If the last element that the algorithm reads is $x$ then it should output $x$ if it had read the elements in $S_1$, and it should output nothing if it has read the elements in $S_2$.

Since there are $\binom{|U|}{n-1} = \binom{n^C}{n-1}$ different sets $S$ and $n^m$ different memory settings, we conclude that $\binom{n^C}{n-1} \leq n^m$. Since $\binom{a}{b} \geq (a/b)^b$, we conclude that $(n^{C-1})^n \lesssim n^m$, and so $(C-1)n \leq m$ or $m = \Omega(n)$ (for $C > 1$).

The reference for the proof the lecture refers to is:

N. Alon, T. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1999.

http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf

You'll find the reult you're looking for in §3.7.