<p>I also recommend reading section 8.1.3 "Frequent-Pattern Mining in Data Streams" of the following book:</p>

<p>Jiawei Han, Micheline Kamber. Data Mining---Concepts and Techniques, Second Edition, <em>Morgan Kaufmann Publishers</em>, 2006.</p>

<p>It introduces an algorithm, known as <strong>Lossy Counting</strong>, which approximates frequent items (items whose support is above some <em>min_support</em>) with arbitrary precision.</p>

<p>Not exactly what you want, but I thought it might help.</p>

CC BY-SA 3.0
2018-03-01T17:03:12.357Z
maybe you can help me on my question [here](https://cstheory.stackexchange.com/questions/40305/complexity-of-lossy-counting)
user1
CC BY-SA 2.5
2010-09-16T02:51:07.407Z
2010-09-16T02:51:07.407Z
Sadeq Dousti
<p>There's an extensive literature on this problem. Firstly, even for $k=1$, the problem is hard: as <a href="http://portal.acm.org/citation.cfm?id=237823" rel="nofollow">Alon, Matias and Szegedy</a> show, you can't get a better than constant factor approximation to the frequency of the most popular element in $o(n)$ space, even if you're willing to be randomized. </p>

<p>However, if you're guaranteed that one element occurs strictly more than 50% of the time, then there's a simple trick that uses constant space and will find it (this is a popular google puzzle question). More generally, you can find elements that occur more than $n/k$ times using a generalization of this trick. </p>

<p>A definitive survey of what's known about the problem is the paper by <a href="http://dimacs.rutgers.edu/~graham/pubs/papers/freq.pdf" rel="nofollow">Cormode and Hadjileftheriou from VLDB 2008</a>. It covers the above methods and many of the latest methods. the general idea is that you can generate an approximate list of the top $k$ items (where approximate here means that you might get items whose counts are close to the counts of the top $k$ items). </p>

CC BY-SA 2.5
2010-09-15T06:27:47.523Z
+1. I think the > 50% of the time algorithm is a well known one (majority element algorithm) as you mentioned
dhruvbird
CC BY-SA 2.5
2010-09-15T06:29:55.893Z
Thanks!! The paper by Cormode and Hadjileftheriou that you mentioned cites this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889 which has the same technique which I was thinking about. It maintains 2 linked lists; one by frequency and within it another list of all elements with the same frequency.
dhruvbird
CC BY-SA 2.5
2010-09-16T07:50:11.910Z
Here's a link: http://userweb.cs.utexas.edu/users/misra/scannedPdf.dir/FindRepeatedElements.pdf
Suresh Venkat
CC BY-SA 2.5
2010-09-16T09:45:36.900Z
This is a comment (not enough reputation) on Suresh Venkat's link http://userweb.cs.utexas.edu/users/misra/scannedPdf.dir/FindRepeatedElements.pdf: It looks like the algorithm presented there requires a second pass through the data, which is not allowed here. In fact, I don't see how a one-pass algorithm with O(1) space requirements can exist.
TonyK
CC BY-SA 2.5
2010-09-16T19:49:24.797Z
the second pass merely verifies. if I have a promise that such an element exists, I don't need to run the second pass. that's the form in which the problem is usually stated.
Suresh Venkat
CC BY-SA 3.0
2010-09-15T06:05:54.003Z
2014-12-01T08:04:57.287Z
2014-12-01T08:04:57.287Z
Suresh Venkat
<p>I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: <a href="https://cstheory.stackexchange.com/questions/1290/divide-and-conquer-data-stream-algorithms">&quot;Divide and conquer&quot; data stream algorithms</a> got me interested in it.</p>

<p>For example, suppose there are numbers: (4,3,5,1,6,2,4,3,3,8,9,1) and I query for the 3 most frequently occurring numbers (say), then I should get (3,4,1) as the answer.</p>

<p>I tried searching online, but couldn't find any place that gives an approach and says that that is the best. A trivial solution would be to use a heap or a balanced binary tree, but I think there is a better way and I wanted to know if it is documented somewhere.</p>

<p>Edit: I'm looking for an algorithm that always gives the correct answer as opposed to a appromixation algorithm (many of which pop up in search results) which rely on the distribution of data in some way or other</p>

CC BY-SA 2.5
2010-09-15T06:26:14.223Z
Actually there are three kinds of algorithms: exact, approximate, and "data dependent". You ruled out the last kind, but are approximate algorithms that do NOT depend on the data distribution permissible ? as I indicated, if not, you're in trouble because of known lower bounds for this problem in a stream setting.
Suresh Venkat
CC BY-SA 2.5
2010-09-15T06:35:35.163Z
I was curious as to whether algorithms that use limited memory (streaming algorithms) can actually do what I wanted and it seems that they can't as you have pointed out. Also whether a non-streaming exact algorithm is known which solves the problem in O(n) guaranteed worst-case time, which mentioned here (cited by the paper by Cormode and Hadjileftheriou from the link you provided): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889
dhruvbird
<ds.algorithms><online-algorithms><data-streams>
Algorithm for 'k'' most frequently occurring numbers
dhruvbird
# Algorithm for 'k'' most frequently occurring numbers

(Asked by: username_0 on 2010-09-15)

I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: ["Divide and conquer" data stream algorithms](https://cstheory.stackexchange.com/questions/1290/divide-and-conquer-data-stream-algorithms) got me interested in it.

For example, suppose there are numbers: (4,3,5,1,6,2,4,3,3,8,9,1) and I query for the 3 most frequently occurring numbers (say), then I should get (3,4,1) as the answer.

I tried searching online, but couldn't find any place that gives an approach and says that that is the best. A trivial solution would be to use a heap or a balanced binary tree, but I think there is a better way and I wanted to know if it is documented somewhere.

Edit: I'm looking for an algorithm that always gives the correct answer as opposed to a appromixation algorithm (many of which pop up in search results) which rely on the distribution of data in some way or other

**Tags:** ds.algorithms, online-algorithms, data-streams

> **Comments:**
> **username_1**: Actually there are three kinds of algorithms: exact, approximate, and "data dependent". You ruled out the last kind, but are approximate algorithms that do NOT depend on the data distribution permissible ? as I indicated, if not, you're in trouble because of known lower bounds for this problem in a stream setting.  
> **username_0**: I was curious as to whether algorithms that use limited memory (streaming algorithms) can actually do what I wanted and it seems that they can't as you have pointed out. Also whether a non-streaming exact algorithm is known which solves the problem in O(n) guaranteed worst-case time, which mentioned here (cited by the paper by Cormode and Hadjileftheriou from the link you provided): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889  

---

## 2 answers

### Answer by username_1 on 2010-09-15. Score: 20 | Accepted answer

There's an extensive literature on this problem. Firstly, even for $k=1$, the problem is hard: as [Alon, Matias and Szegedy](http://portal.acm.org/citation.cfm?id=237823) show, you can't get a better than constant factor approximation to the frequency of the most popular element in $o(n)$ space, even if you're willing to be randomized.

However, if you're guaranteed that one element occurs strictly more than 50% of the time, then there's a simple trick that uses constant space and will find it (this is a popular google puzzle question). More generally, you can find elements that occur more than $n/k$ times using a generalization of this trick.

A definitive survey of what's known about the problem is the paper by [Cormode and Hadjileftheriou from VLDB 2008](http://dimacs.rutgers.edu/~graham/pubs/papers/freq.pdf). It covers the above methods and many of the latest methods. the general idea is that you can generate an approximate list of the top $k$ items (where approximate here means that you might get items whose counts are close to the counts of the top $k$ items).

> **Comments:**
> **username_0**: +1. I think the > 50% of the time algorithm is a well known one (majority element algorithm) as you mentioned  
> **username_0**: Thanks!! The paper by Cormode and Hadjileftheriou that you mentioned cites this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889 which has the same technique which I was thinking about. It maintains 2 linked lists; one by frequency and within it another list of all elements with the same frequency.  
> **username_1**: Here's a link: http://userweb.cs.utexas.edu/users/misra/scannedPdf.dir/FindRepeatedElements.pdf  
> **username_4**: This is a comment (not enough reputation) on username_1's link http://userweb.cs.utexas.edu/users/misra/scannedPdf.dir/FindRepeatedElements.pdf: It looks like the algorithm presented there requires a second pass through the data, which is not allowed here. In fact, I don't see how a one-pass algorithm with O(1) space requirements can exist.  
> **username_1**: the second pass merely verifies. if I have a promise that such an element exists, I don't need to run the second pass. that's the form in which the problem is usually stated.  

---

### Answer by username_2 on 2010-09-16. Score: 2

I also recommend reading section 8.1.3 "Frequent-Pattern Mining in Data Streams" of the following book:

Jiawei Han, Micheline Kamber. Data Mining---Concepts and Techniques, Second Edition, *Morgan Kaufmann Publishers*, 2006.

It introduces an algorithm, known as **Lossy Counting**, which approximates frequent items (items whose support is above some *min\_support*) with arbitrary precision.

Not exactly what you want, but I thought it might help.

> **Comments:**
> **username_3**: maybe you can help me on my question [here](https://cstheory.stackexchange.com/questions/40305/complexity-of-lossy-counting)  

---

