Re:Damn Cool Algorithms: Cardinality Estimation
by nicksdjohnson on Friday September 07, 2012 @10:35AM
(#4489272)
Very nice, thanks! It might be too similar for a post all of its own, but I think it'd be a worthy followup to this post.
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.
http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASim...