# frequency moments

Published articles for frequency moments.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Finding the majority element of a stream

DevFeed: [Finding the majority element of a stream](<https://devfeed.tech/articles/finding-the-majority-element-of-a-stream-40379.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2015/03/09/finding-the-majority-element-of-a-stream/>)

Published: 2015-03-09T09:00:11Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [Python](<https://devfeed.tech/topics/python.md>), [data](<https://devfeed.tech/topics/data.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [counter](<https://devfeed.tech/tags/counter.md>), [data-mining](<https://devfeed.tech/tags/data-mining.md>), [frequency-moments](<https://devfeed.tech/tags/frequency-moments.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [pair](<https://devfeed.tech/tags/pair.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [space](<https://devfeed.tech/tags/space.md>), [stream](<https://devfeed.tech/tags/stream.md>), [streaming-algorithms](<https://devfeed.tech/tags/streaming-algorithms.md>), [streaming-data](<https://devfeed.tech/tags/streaming-data.md>), [sublinear-space](<https://devfeed.tech/tags/sublinear-space.md>)

### AI overview

This article presents a Python algorithm for finding the value that occurs more than half the time in a massive data stream. It explains the pairing-based correctness argument, single-pass operation, O(log(n) + log(m)) space usage, the necessity of the majority guarantee, and a k-counter generalization for detecting frequent items.

### Source excerpt

Problem: Given a massive data stream of $ n$ values in $ \{ 1, 2, \dots, m \}$ and the guarantee that one value occurs more than $ n/2$ times in the stream, determine exactly which value does so. Solution: (in Python) def majority(stream): held = next(stream) counter = 1 for item in stream: if item == held: counter += 1 elif counter == 0: held = item counter = 1 else: counter -= 1 return held Discussion: Let's prove correctness.