Optimal streaming histograms
blog.amplitude.com
Optimal streaming histograms
1–10 of 20 posts
Re: Optimal streaming histograms
#2The optimal number of bins has a rich statistics literature. The Freedman-Diaconis Rule is a good place to start: http://en.wikipedia.org/wiki/Freedman%E2%80%93Diaconis_rule
That said, the challenge with online (streaming) data is that you have to constantly estimate the distribution you are sampling from. Someone here might know better =)
Re: Optimal streaming histograms
#3Could you not keep statistics on the values that went into each bucket, and use those to redistribute the contents of the bucket when the buckets needed to be resized?
Sure, it's an estimate so you'd have some error term but you could pass that on to the new buckets. If the total error is small enough in practice it wouldn't be a problem.
Re: Optimal streaming histograms
#4Hive seems to use something similar to the 2nd algorithm (merging close bins together):
https://svn.apache.org/repos/asf/hive/trunk/ql/src/java/org/...
Re: Optimal streaming histograms
#5Technique #4 would be extremely interesting if a user could click into a bucket and drop to the appropriate resolution level. Using their example, the user could click on the big yellow bar at 290 and see the .1-increment buckets for a 10-sized distribution.
Re: Optimal streaming histograms
#6Could you not keep statistics on the values that went into each bucket, and use those to redistribute the contents of the bucket when the buckets needed to be resized? Sure, it's an estimate so you'd have some error term but you could pass that on to the new buckets. If the total error is small enough in practice it wouldn't be a problem.
One of the problems we had to solve is compressing the data set so you don't need to keep too many bins around. To get one more significant figure, you need to keep 10x the number of bins. Once you have those individual bins you can always merge them in the visualization, the problem is defining them in a way that covers the distribution and doesn't take up too much space.
Re: Optimal streaming histograms
#7The optimal number of bins has a rich statistics literature. The Freedman-Diaconis Rule is a good place to start: http://en.wikipedia.org/wiki/Freedman%E2%80%93Diaconis_rule That said, the challenge with online (streaming) data is that you have to constantly estimate the distribution you are sampling from. Someone here might know better =)
I worked in R&D for an extremely large ag company. We found that .5 or 1 STD bucket sizes seemed to work pretty well
Re: Optimal streaming histograms
#8There are some nice, very efficient implementations of their solution #4at http://hdrhistogram.github.io/HdrHistogram/
Re: Optimal streaming histograms
#9A cute one I have been meaning to try: using a Haar wavelet as the histogram, with online updates.
theory.stanford.edu/~matias/papers/wavelets-vldb00.pdf
Re: Optimal streaming histograms
#10Log-binning can be useful. However it has some disadvantages.
I think that in your case your data (server response time?) looks good because you probably have a log-logistic or log-normal distribution.
Suppose you were working with values that are exponentially distributed which is also a reasonable hypothesis for your data. In that case the log-binned histogram would like a plateau with the exception of the beginning and ending bins. In this scenario a linear-binning approach would probably be better.
Unfortunately, I think that there is no approach for bucketing that is good for all situations. Usually the best approach will depend on your data and also on what you are trying to analyze.