Finding the Majority Item in a Stream

Going through old CACM issues I discovered a paper (PDF) on stream processing. A common problem in this field is to find frequent items in a data stream when you only get one pass through the data and you need answers in real time. This is interesting in situations where you don’t have enough memory to store counters for each distinct item you see in the stream. One example is keeping track of the most frequent destinations in a high traffic network router.

Among others, the authors present the classic Majority algorithm that finds the majority item in a stream. An item is the majority item if it occurs more than 50% of the time.

Here’s an implementation in Python with an example stream of integers:

stream = (1, 2, 3, 1, 3, 3, 1, 3, 2, 3, 3)

majority = stream[0]
counter = 1
for item in stream[1:]:
    if item == majority:
        counter += 1
    else:
        if counter == 0:
            majority = item
            counter = 1
        else:
            counter -= 1

print majority

One drawback of this and the other presented algorithms is that the algorithm always flags one item as the majority. But without a second pass you can’t actually tell if it’s really a majority. The algorithm just guarantees that if there is a majority item, then it will give it to you. This sounds like a big drawback, but there are cases where you know the frequency distribution of your items and you can tell beforehand that there will be a majority.

The other algorithms presented in the paper are generalizations that find all k items that exceed a 1/k fraction of the total number of items. They are useful when you know that a few items occur a lot of the time while most items are quite rare (see Power Law Distribution). Page impressions on your website could be an example, or the frequency of certain words in a natural language.

Advertisements
This entry was posted in computer science and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s