News for hackers. Stuff that matters.
Re:Data trumps everything by chubot on Saturday January 12, 2013 @11:56PM (#5050018)
They're not really statistical algorithms -- you certainly wouldn't learn them in a statistics class.

I actually looked online for some references on streaming algorithms ... but somewhat surprisingly, I couldn't find anything really. I realized a lot of this knowledge has been hard-earned, I guess that is good :) But there really should be a reference.

Definitely look up "reservoir sampling", which gives you a fixed size sample of an infinite length stream. This algorithm has come up over and over for me, and I've implemented it in multiple contexts. There is a way to do it in MapReduce which is very useful.

You know probably the most condensed version I can think of is quite hidden: see the open source Sawzall code:

http://code.google.com/p/szl/source/browse/#svn%2Ftrunk%2Fsr...

All those functions aggregate some property of a stream. Someone (maybe me if I finish the 30 projects I've started...) really should write up some real documentation about all those algorithms, because they're not only fun, but useful.

A lot of them are (necessarily) approximations. You don't learn that many approximate algorithms in a traditional CS class. None of this will be in any stats class for sure.

There are no comments on this comment yet.