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

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

blog.timescale.com

Post reply on HN
Print view View original

11–20 of 173 posts

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

#11

Post by djk447 »

madars wrote: post #8

Good opportunity to plug https://en.wikipedia.org/wiki/Anscombe%27s_quartet : if you don't know much about the underlying distribution, simple statistics don't describe it well. From Wikipedia description: Anscombe's quartet comprises four data sets that have nearly identical simple descriptive statistics, yet have very different distributions and appear very different when graphed. Each dataset consists of eleven (x…

NB: Post author here.

That's really nifty, wish I'd heard about it earlier. Might go back and add a link to it in the post at some point too! Very useful. Definitely know I wasn't breaking new ground or anything, but fun to see it represented so succinctly.

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

#12

Post by waynecochran »

djk447 wrote: post #9
achenatx wrote: post #6

Ive been trying to get the marketing team to always include a std deviation with averages. Average alone is simply not useful, standard deviation is a simple way to essentially include percentiles. They regularly compare experiments to the mean but dont use a T test to ensure the results are actually different from the mean.

NB: Post author here. Std deviation definitely helps a lot, still often not as good as percentiles, was actually thinking about adding some of that in the post but it was already getting so long. It's funny how things you think are simple sometimes take the most effort to explain, definitely found that on this one.

Yeah -- std deviation has a similar problem to the mean in that it doesn't give you a full picture unless the distribution is close to normal / gaussian.

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

#13

Post by cyral »

bqe wrote: 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 "…

There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%)

[1]: https://arxiv.org/pdf/1902.04023.pdf / https://github.com/tdunning/t-digest

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

#14

Post by djk447 »

bqe wrote: 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 "…

NB: Post author here.

Thanks for sharing! Hadn't heard of that algorithm, have seen a number of other ones out there, we chose a couple that we knew about / were requested by users. (And we are open to more user requests if folks want to use other ones! https://github.com/timescale/timescaledb-toolkit and open an issue!)

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

#15

Post by convolvatron »

cyral wrote: post #13
bqe wrote: 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 "…

There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%) [1]: https://arxiv.org/pdf/1902.04023.pdf / https://github.com/tdunning/t-digest

i think the new ones started wtih Greenwald-Khanna. but i definately agree - p^2 can be a little silly and misleading. in particular it is really poor at finding those little modes on the tail that correspond to interesting system behaviours.

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

#16

Post by cyral »

convolvatron wrote: post #15
cyral wrote: post #13

Earlier quoted context omitted.

There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%) [1]: https://arxiv.org/pdf/1902.04023.pdf / https://github.com/tdunning/t-digest

i think the new ones started wtih Greenwald-Khanna. but i definately agree - p^2 can be a little silly and misleading. in particular it is really poor at finding those little modes on the tail that correspond to interesting system behaviours.

That sounds familiar, I remember reading about Greenwald-Khanna before I found T-Digest after I ran into the "how to find a percentile of a massive data set" problem myself.

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

#17

Post by varelaz »

Percentiles for sure are better than average if you want to explore distribution: there are several percentiles comparing to single average. However median is harder to use if you want to do calculations based on this metric. For example distribution of sample median could be a problem, if you want to understand confidence interval for it for example.

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

#18

Post by djk447 »

tunesmith wrote: post #2

I just recently tried giving a presentation to my department (they're developers, I'm architect) about this stuff and they all just sort of blinked at me. It brought in Little's Law and Kingman's Formula, in an attempt to underscore why we need to limit variation in the response times of our requests. There are a bunch of queuing theory formulas that are really cool but don't exactly apply if your responses vary a lo…

NB: Post author here.

I found it surprisingly difficult to explain well. Took a lot of passes and a lot more words than I was expecting. It seems like such a simple concept. I thought the post was gonna be the shortest of my recent ones, and then after really explaining it and getting lots of edits and rewriting, it was 7000 words and ...whoops! But I guess it's what I needed to explain it well (hope you thought so anyway).

It's somewhat exponential, but yeah, not necessarily, it's definitely long-tailed in some way and it sort of doesn't matter what the theoretical description is (at least in my mind) the point is these types of distributions really don't get described well by a lot of typical statistics.

Can't talk too much about SREs at the ad analytics company I mentioned, we were the backend team that wrote a lot of the backend stores / managed databases / ran the APIs and monitored this stuff a bit (and probably not all that well). It was a bit more ad hoc I guess, probably now that company is large enough they have a dedicated team for that...

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

#19

Post by doctorsher »

achenatx wrote: post #6

Ive been trying to get the marketing team to always include a std deviation with averages. Average alone is simply not useful, standard deviation is a simple way to essentially include percentiles. They regularly compare experiments to the mean but dont use a T test to ensure the results are actually different from the mean.

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 completely different distributions, with identical mean and standard deviation (among other things). Histograms and percentiles, and if necessary their approximations, are more desirable for the above reasons.

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

#20

Post by djk447 »

varelaz wrote: post #17

Percentiles for sure are better than average if you want to explore distribution: there are several percentiles comparing to single average. However median is harder to use if you want to do calculations based on this metric. For example distribution of sample median could be a problem, if you want to understand confidence interval for it for example.

NB: Post author here.

Totally can be true. In our case, we use these approximation methods that allow you to get multiple percentiles "for free" definitely need to choose the right ones for the job. (We talk a bit more about the whole approach where we do the aggregation then the accessor thing in the previous post on two-step aggregation [1]). But there are definitely times when averages/stddev and potentially the 3rd and 4th moments are more useful etc.

[1]: https://blog.timescale.com/blog/how-postgresql-aggregation-w...

Post reply on HN