Top-k frequent items in data stream

Question

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?

Answer 1

Alon, Matias, and Szegedy 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 gave a very nice overview of the known $k$-HH algorithms, with brief descriptions, space complexity, and experimental results for performance.

Answer 2

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.