Hmmmm... my gut reaction is to consider reframing the question. Do you really need to know the shape of the distribution, or is it sufficient to know, say, var

Hmmmm... my gut reaction is to consider reframing the question. Do you really need to know the shape of the distribution, or is it sufficient to know, say, various percentiles (e.g. 50%, 75%, 99%, 99.9%). If you're looking at metrics like response time usually 99% is all you care about. If this is the case there are efficient algorithms to estimate these values from streaming data using O(1) space with high probability bounds on error. If you just need counts indexed by some key, then the count-min sketch might be sufficient (e.g. http://www.auai.org/uai2012/papers/231.pdf http://www.auai.org/uai2012/papers/231.pdf) Finally, if you really do need to know the shape of the distribution should you be considering kernel density estimation (KDE) instead of histograms (see http://en.wikipedia.org/wiki/Kernel_density_estimation http://en.wikipedia.org/wiki/Kernel_density_estimation)? Most people would argue you should. Looks like there are streaming KDE algorithms, though I don't know how practical they are.