4 ms·
It sounds like the sampling and streaming algorithms you know are statistical algorithms. Have you got any good references for streaming algorithms?
by alexchamberlain 14y ago
It sounds like the sampling and streaming algorithms you know are statistical algorithms. Have you got any good references for streaming algorithms?
- chubot 14y agoThey'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%2Fsrc%2Femitters 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.