The Majority Event In Streaming Data

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

Arun Jagota

545 Followers

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.