Re:Damn Cool Algorithms: Cardinality Estimation
by beder on Friday September 07, 2012 @11:46AM
(#4489664)
You can do a second pass over the list to check that your solution is actually a majority element. This maintains the linear time and constant space properties.
Re:Damn Cool Algorithms: Cardinality Estimation
by justincormack on Friday September 07, 2012 @06:06PM
(#4491427)
Unfortunately single pass is usually the binding constraint eg real time data processing.
Note that this algorithms fails silently if there is not majority element, which limits the scope of its utility.
I assume that the reason it took so long to discover is that no one needed the solution before. Are there applications that can benefit form this algorithm?