Live data from Hacker News

How percentile approximation works and why it's more useful than averages

blog.timescale.com

121–130 of 173 posts

Re: How percentile approximation works and why it's more useful than averages

#121

Looking particularly at latency measurements, I found the "How NOT to Measure Latency" [1] talk very illuminating. It goes quite deep into discussing how percentiles can be used and abused for measurement. [1]: https://www.infoq.com/presentations/latency-response-time/

What are some of the ways percentiles can be abused?

Re: How percentile approximation works and why it's more useful than averages

#122
post #111

Earlier quoted context omitted.

I watch this video once a year and send it to my co-workers whenever averages or medians shows up in a graph for public consumption.

Are the points written in a readable format anywhere?

http://highscalability.com/blog/2015/10/5/your-load-generato...

Discussed previously: https://news.ycombinator.com/item?id=10334335

Re: How percentile approximation works and why it's more useful than averages

#124

Earlier quoted context omitted.

I heavily caution against the feeling that "standard deviation is a simple way to essentially include percentiles." The usefulness of the standard deviation depends on the distributions that you are working with. Heavy tailed distributions appear a fair amount in practice, and the combo of summary statistics mentioned would not do well on those. Also, Madars' comment in this thread is a beautiful example of this: 4 c…

I assume most of the distributions a marketing department would be dealing with are generally normal in which case stddev is a great way to analyze the data. This can be easily verified by just plotting said data and making sure the tails don't look weird.

I can't help but idly wonder what humans are doing when they are eyeballing the tails, to see if things look good. Like lets say we wanted to do the eyeball test but automatically. Would the best way be to use an image classifier on the plot? Is there something magic about the plot representation that would make it good even for computers to use?

Re: How percentile approximation works and why it's more useful than averages

#125

I really enjoyed this post! The author also wrote an interactive demonstration of the concepts (using Desmos). It's super helpful. https://www.desmos.com/calculator/ty3jt8ftgs

NB: Post author here.

Glad you liked it! I was so excited to actually be able to get to use Desmos for something work wise, I've been wanting to do it for years!

Re: How percentile approximation works and why it's more useful than averages

#126
If you want to calculate exact percentiles there's a simple in-place algorithm that runs in expected O(n) time. You basically do quicksort but ignore the "wrong" partition in each recursive step. For instance if your pivot is at the 25% percentile and you're looking for the 10% percentile you only recurse on the "left" partition at that point. It's pretty easy to implement. (And rather straightforward to change to a loop, if necessary.)

Re: How percentile approximation works and why it's more useful than averages

#127
post #103

Earlier quoted context omitted.

i think of it as: if the data is gaussian, use a mean, otherwise go non-parametric (medians/percentiles). or put another way, if you can't model it, you're going to have to sort, or estimate a sort, because that's all that's really left to do. this shows up in things from estimating centers with means/percentiles to doing statistical tests with things like the wilcoxon tests.

Assume up front none of your measured latencies from a software networked system will be Gaussian, or you will die a painful death . Even ping times over the internet have no mean. The only good thing about means is you can combine them easily, but since they are probably a mathematical fiction, combining them is even worse. Use T-Digest or one of the other algorithms being highlighted here.

This is why I try to plot a proper graph of times from any "optimization" I see in a PR. Too many times I see people making this assumption for example, and even if they're right they usually forget to take the width of the gaussian into account (i.e. wow your speedup is 5% of a standard deviation!)

Re: How percentile approximation works and why it's more useful than averages

#128
post #106
post #27

Earlier quoted context omitted.

Barchart is basically your percentiles (just more of them) so why not show it? Bars and whiskers could be more complicated for them but still the same sort of data

Barcharts across categorical data :P That is, the first bar is "Our Number" and the second bar is "Competitor's number."

Someone clearly gets it. Variability viz and spread detracts from that clear message.

Re: How percentile approximation works and why it's more useful than averages

#129
post #3

Awhile ago I wrote a Python library called LiveStats[1] that computed any percentile for any amount of data using a fixed amount of memory per percentile. It uses an algorithm I found in an old paper[2] called P^2. It uses a polynomial to find good approximations. The reason I made this was an old Amazon interview question. The question was basically, "Find the median of a huge data set without sorting it," and the "…

> Find the median ... randomly evict items So, not find, but approximate. That's a different thing.

> without sorting it... have a fixed size sorted buffer

(that you sort yourself)

Re: How percentile approximation works and why it's more useful than averages

#130
post #3

Awhile ago I wrote a Python library called LiveStats[1] that computed any percentile for any amount of data using a fixed amount of memory per percentile. It uses an algorithm I found in an old paper[2] called P^2. It uses a polynomial to find good approximations. The reason I made this was an old Amazon interview question. The question was basically, "Find the median of a huge data set without sorting it," and the "…

> The question was basically, "Find the median of a huge data set without sorting it," Isn't this done using a min heap and a max heap in conjuction?

How does this get you the median?
Post reply on HN