The Majority Event In Streaming Data

An interesting (and idiosyncratic) streaming algorithm

Imagine a possibly unbounded stream of incoming symbols. At a particular point, say there is some symbol that has occurred more than 50% of the time till then. We call it a majority symbol. It is obviously unique if it exists.

This post discusses an efficient streaming algorithm that “half” solves this problem. If the stream has a majority symbol, it finds it. (This is equivalent to saying that if the algorithm outputs NO, the stream for sure doesn’t…

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arun Jagota

PhD, Computer Science, neural nets. 14+ years in industry: data science algos developer. 24+ patents issued. 50 academic pubs. Blogs on ML/data science topics.