20
$\begingroup$

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 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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 15, 2010 at 6:26
  • 1
    $\begingroup$ 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): citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889 $\endgroup$
    – dhruvbird
    Sep 15, 2010 at 6:35

2 Answers 2

20
$\begingroup$

There's an extensive literature on this problem. Firstly, even for $k=1$, the problem is hard: as Alon, Matias and Szegedy 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. 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).

$\endgroup$
6
  • 1
    $\begingroup$ +1. I think the > 50% of the time algorithm is a well known one (majority element algorithm) as you mentioned $\endgroup$
    – dhruvbird
    Sep 15, 2010 at 6:27
  • 2
    $\begingroup$ Thanks!! The paper by Cormode and Hadjileftheriou that you mentioned cites this paper: 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. $\endgroup$
    – dhruvbird
    Sep 15, 2010 at 6:29
  • $\begingroup$ can you elaborate on the more than 50 percent algorithm ? and the google puzzle ? I cannot follow this sloppy reasoning as you have just touched on it and not fully expended upon "the well -known trick". Thanks. $\endgroup$
    – Paul Smith
    Sep 16, 2010 at 7:06
  • $\begingroup$ Here's a link: userweb.cs.utexas.edu/users/misra/scannedPdf.dir/… $\endgroup$ Sep 16, 2010 at 7:50
  • $\begingroup$ This is a comment (not enough reputation) on Suresh Venkat's link userweb.cs.utexas.edu/users/misra/scannedPdf.dir/…: 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. $\endgroup$
    – TonyK
    Sep 16, 2010 at 9:45
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ maybe you can help me on my question here $\endgroup$
    – user1
    Mar 1, 2018 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.