News for hackers. Stuff that matters.
Re:Damn Cool Algorithms: Cardinality Estimation by lurker14 on Friday September 07, 2012 @11:37AM (#4489616)
Direct link to the pre-generalized: https://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

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?

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.