<p><a href="http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf" rel="noreferrer">Alon, Matias, and Szegedy</a> proved that finding the frequency of the most frequent of $n$ items requires $\Omega(n)$ space in the worst case in the streaming model, even if you allow a constant number of passes over the input. Since finding the most frequent item gives you a two-pass algorithm for computing its frequency (find in the first pass, track its frequency in the second), we cannot find the most frequent item in sublinear space in the streaming model. </p>

<p>Usually the way to deal with such a lower bound is to relax the problem. The algorithms Massimo mentions are for the most popular relaxation: the $k$-Heavy Hitters problem ($k$-HH). The $k$-HH problem asks to output all items whose frequency is at least $\frac{m}{k}$, where $m$ is the total frequency of all items (i.e. the length of the stream, in the simplest streaming model). So in $k$-HH we ´expect to see an item only if it actually is very frequent. This problem requires linear space to solve exactly as well: i.e. an algorithm which outputs all and only the items of frequency $\geq \frac{m}{k}$ requires $\Omega(n)$ space in the worst case. For this reason, the problem is usually relaxed a little further: we expect a $k$-HH algorithm to output all items of frequency at least $\frac{m}{k}$ and no items of frequency less than $\frac{(1-\varepsilon)m}{k}$. All algorithms Massimo lists actually do that.</p>

<p><a href="http://dimacs.rutgers.edu/~graham/pubs/papers/freq.pdf" rel="noreferrer">Cormode and Hadjieleftheriou</a> gave a very nice overview of the known $k$-HH algorithms, with brief descriptions, space complexity, and experimental results for performance. </p>

CC BY-SA 3.0
2013-11-14T15:05:04.877Z
2015-06-22T13:09:09.060Z
2015-06-22T13:09:09.060Z
Sasho Nikolov
<p>Frequent items can be found using either $count$-based or $sketch$-based algorithms; these algorithms may be adapted to answer top-$k$ queries as well.</p>

<p>For count-based algorithms, Space Saving can report frequent items in time linear in $O(n)$, the total number of items using $k$ counters. The Frequent algorithm reports frequent items in $O(n)$ time using $k-1$ counters.</p>

<p>Among the sketch-based algorithms, relevant algorithms include Count-Min which uses $O(1/\epsilon \log 1/\delta )$ space and hCount whose space complexity is better, being $O(1/\epsilon \log(-M/(\log 1- \delta)))$, where $\epsilon, \delta, M$ are input parameters.</p>

<p>These algorithms also works for streams. Note that the space complexities reported are for heavy-hitters and not for top$k$ queries. See Sasho's answer.</p>

CC BY-SA 3.0
2013-11-14T14:48:35.413Z
Massimo, these are for heavy hitters. top-$1$ already requires linear space in the worst case.
Sasho Nikolov
CC BY-SA 3.0
2013-11-14T15:58:48.167Z
Sasho, you are right. I gave these indications since the algorithms are easily modified to answer top-$k$ queries as well, but I mistakenly reported the space complexities for heavy hitters alone. Mea culpa ;-)
Massimo Cafaro
CC BY-SA 3.0
2013-11-14T12:10:48.230Z
2013-11-15T14:43:32.397Z
2013-11-15T14:43:32.397Z
Massimo Cafaro
<p>Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set.</p>

<p>I am thinking about few related question:</p>

<ol>
<li><p>Given a large data set (total data size is known), how to find top k frequent items? better to use less space. 
Simple approach(count frequency of each item in data set, and sort) requires lots of space</p></li>
<li><p>What about finding top k frequent items in data stream?</p></li>
</ol>

<p>Is there any near-optimal algorithms avaiable? or, can we prove relationship between space requirement and error ratio?</p>

<approximation-algorithms><lower-bounds>
Top-k frequent items in data stream
xbob.ym
# Top-k frequent items in data stream

(Asked by: username_0 on 2013-11-14)

Paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" introduce an efficient algorithm which can help to estimate distinct items in large data set.

I am thinking about few related question:

1. Given a large data set (total data size is known), how to find top k frequent items? better to use less space.
   Simple approach(count frequency of each item in data set, and sort) requires lots of space
2. What about finding top k frequent items in data stream?

Is there any near-optimal algorithms avaiable? or, can we prove relationship between space requirement and error ratio?

**Tags:** approximation-algorithms, lower-bounds

---

## 2 answers

### Answer by username_1 on 2013-11-14. Score: 10

[Alon, Matias, and Szegedy](http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf) proved that finding the frequency of the most frequent of $n$ items requires $\Omega(n)$ space in the worst case in the streaming model, even if you allow a constant number of passes over the input. Since finding the most frequent item gives you a two-pass algorithm for computing its frequency (find in the first pass, track its frequency in the second), we cannot find the most frequent item in sublinear space in the streaming model.

Usually the way to deal with such a lower bound is to relax the problem. The algorithms Massimo mentions are for the most popular relaxation: the $k$-Heavy Hitters problem ($k$-HH). The $k$-HH problem asks to output all items whose frequency is at least $\frac{m}{k}$, where $m$ is the total frequency of all items (i.e. the length of the stream, in the simplest streaming model). So in $k$-HH we ´expect to see an item only if it actually is very frequent. This problem requires linear space to solve exactly as well: i.e. an algorithm which outputs all and only the items of frequency $\geq \frac{m}{k}$ requires $\Omega(n)$ space in the worst case. For this reason, the problem is usually relaxed a little further: we expect a $k$-HH algorithm to output all items of frequency at least $\frac{m}{k}$ and no items of frequency less than $\frac{(1-\varepsilon)m}{k}$. All algorithms Massimo lists actually do that.

[Cormode and Hadjieleftheriou](http://dimacs.rutgers.edu/~graham/pubs/papers/freq.pdf) gave a very nice overview of the known $k$-HH algorithms, with brief descriptions, space complexity, and experimental results for performance.


---

### Answer by username_2 on 2013-11-14. Score: 3

Frequent items can be found using either $count$-based or $sketch$-based algorithms; these algorithms may be adapted to answer top-$k$ queries as well.

For count-based algorithms, Space Saving can report frequent items in time linear in $O(n)$, the total number of items using $k$ counters. The Frequent algorithm reports frequent items in $O(n)$ time using $k-1$ counters.

Among the sketch-based algorithms, relevant algorithms include Count-Min which uses $O(1/\epsilon \log 1/\delta )$ space and hCount whose space complexity is better, being $O(1/\epsilon \log(-M/(\log 1- \delta)))$, where $\epsilon, \delta, M$ are input parameters.

These algorithms also works for streams. Note that the space complexities reported are for heavy-hitters and not for top$k$ queries. See Sasho's answer.

> **Comments:**
> **username_1**: Massimo, these are for heavy hitters. top-$1$ already requires linear space in the worst case.  
> **username_2**: Sasho, you are right. I gave these indications since the algorithms are easily modified to answer top-$k$ queries as well, but I mistakenly reported the space complexities for heavy hitters alone. Mea culpa ;-)  

---

