Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Optimal streaming histograms

blog.amplitude.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Optimal streaming histograms

#11

Post by CraigJPerry »

Crap. I wish i didn't read the HN comments page now. I read the first sentence of the article and immediately thought "you could bin on a log scale".

To be clear this isn't an area i'd consider myself all that knowledgeable. Coming up with a useful idea was an achievement.

So as i read through, comparing each proposed solution to mine, i decided i quite liked mine. Then i see that last proposal is my first idea. Great!

So over i wander to the HN comments and see that this is a common approach, i didn't just come up with a nice neat solution, i probably learned it, forgot it, and regurgitated it from my subconscious.

That sure doesn't feel as nice as the sparkly feeling i had just 3 minutes ago...

Re: Optimal streaming histograms

#12

Post by sskates »

CraigJPerry wrote: post #11

Crap. I wish i didn't read the HN comments page now. I read the first sentence of the article and immediately thought "you could bin on a log scale". To be clear this isn't an area i'd consider myself all that knowledgeable. Coming up with a useful idea was an achievement. So as i read through, comparing each proposed solution to mine, i decided i quite liked mine. Then i see that last proposal is my first idea. Grea…

That's still impressive! It took you two seconds while it took us 3 code iterations to get it right. It seems so obvious in retrospect but in the moment it can be hard to use the full range of your intuition about math. That knowledge could probably have saved us a day or two of coding.

OTOH it's extra difficult because when we did a first implementation we didn't we didn't have a full understanding of the shape of the problem.

Re: Optimal streaming histograms

#13

Post by leeoniya »

CraigJPerry wrote: post #11

Crap. I wish i didn't read the HN comments page now. I read the first sentence of the article and immediately thought "you could bin on a log scale". To be clear this isn't an area i'd consider myself all that knowledgeable. Coming up with a useful idea was an achievement. So as i read through, comparing each proposed solution to mine, i decided i quite liked mine. Then i see that last proposal is my first idea. Grea…

whenever i encounter "orders of magnitude" these days, my brain visualizes a log scale, lol.

Re: Optimal streaming histograms

#14

Post by StefanKarpinski »

Online (i.e. single pass) estimation of quantiles is a well-studied subject – doing some literature research would have gone a long way here. Back in 2004, this was the best paper I found:

http://ftp10.us.freebsd.org/users/azhang/disc/SIGMOD/pdf-fil...

The technique is efficient, straightforward and has provable error bounds. It was published in 2001, so it would also be worth looking at subsequent papers that have cited it for further improvements:

http://scholar.google.com/scholar?cites=6184540005789557130&...

Re: Optimal streaming histograms

#15

Post by calebreach »

You might want to consider using kernel density plots rather than histograms, as histograms exhibit aliasing artifacts.

In general, binning/bucketing can be seen as filtering the empirical density function of your dataset with a box filter and then sampling. The frequency response of a box filter is the sinc function, which has a lot of energy above the Nyquist of this sampling rate. Kernel density plots with a gaussian kernel, on the other hand, can be seen as filtering the empirical density function with a gaussian filter and are thus approximately bandlimited.

Re: Optimal streaming histograms

#16

Post by noelwelsh »

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)

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)? Most people would argue you should. Looks like there are streaming KDE algorithms, though I don't know how practical they are.

Re: Optimal streaming histograms

#17

Post by aroden »

Strikingly similar to the problem of generating a close enough dendrogram over large data sets very quickly. Back in ~2008 I did some undergrad research on the topic to speed DNA analysis. Basically it solves your grouping problem gracefully by attempting to be within a error level at N levels. Since you are attempting N buckets this would solves your problem well. There was a very good review paper on the subject but is not in first page of google and my memory fails me completely on author (also I'm at work).

Might not meet your memory or computation constraints, but grouping is such an wide topic.

Re: Optimal streaming histograms

#18

Post by infinite8s »

StefanKarpinski wrote: post #14

Online (i.e. single pass) estimation of quantiles is a well-studied subject – doing some literature research would have gone a long way here. Back in 2004, this was the best paper I found: http://ftp10.us.freebsd.org/users/azhang/disc/SIGMOD/pdf-fil... The technique is efficient, straightforward and has provable error bounds. It was published in 2001, so it would also be worth looking at subsequent papers that have c…

I've found that people in industry are often unaware of recent discoveries in academia (even if they themselves were once academics). Unfortunately most of the top journals of interest to datascientists are locked behind a paywall, but sometimes Google Scholar is able to find a free copy scraped from some academic's personal site (the "All N versions" link is usually helpful unless the paper was published in an ACM or IEEE journal - those guys seem to hunt down carelessly posted papers on people's private sites).
Post reply on HN