News for hackers. Stuff that matters.
Re:Damn Cool Algorithms: Cardinality Estimation by psykotic on Friday September 07, 2012 @10:28AM (#4489221)
I can't resist mentioning a favorite algorithm of mine for solving a related problem. It generalizes the algorithm for the classic problem of finding the majority element (one which occurs at least 50% of the time) with a single pass over a stream, using a constant amount of space, and a second sieving pass. It's one of those simple gems you wonder why it took so long to discover.

http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASim...

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.