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

41–50 of 173 posts

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

#41

Post by Lockerman »

vvern wrote: post #40
djk447 wrote: post #23

Earlier quoted context omitted.

NB: Post author here. Yeah, that was one of the reasons we chose it as one of the ones to implement, seemed like that was a really interesting tradeoff, we also used uddsketch[1] which provides relative error guarantees, which is pretty nifty. We thought they provided different enough tradeoffs that we wanted to implement both. [1]: https://arxiv.org/abs/1908.10693

Is it using https://github.com/tvondra/tdigest under the hood, or a separate implementation?

a separate implementation

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

#42

Post by djk447 »

hnuser123456 wrote: post #38

Gamers have an intuitive sense of this. Your average framerate can be arbitrarily high, but if you have a big stutter every second between the smooth moments, then a lower but more consistent framerate may be preferable, typically expressed as the 1% and 0.1% slowest frames, which at a relatively typical 100fps, represents the slowest frame every second and every 10 seconds.

NB: Post author here.

Love this example. Might have to use that in a future post. Feel like a lot of us are running into a similar thing with remote work and video calls these days...

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

#43

Post by breuleux »

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

That's pretty neat! Can these be used to efficiently compute rolling percentiles (over windows of the data), or just incremental?

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

#44

Post by monkeydust »

bluesmoon wrote: post #34
axpy906 wrote: post #33

There’s something called a five number summary in statistics: mean, median, standard deviation, 25th percentile and 75th percentile. The bonus is that the 75th - 50th gives you the interquartile range. Mean is not a robust measure and as such you need to look at variety to truly understand the spread of your data.

IQR is 75th - 25th, aka, the middle-50%

Ok this, box plots are a good way to visualize and show distribution esp to a not so stat heavy audience.

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

#45

Post by JackFr »

bluesmoon wrote: post #30

This is exactly the algorithm we developed at LogNormal (now part of Akamai) 10 years ago for doing fast, low-memory percentiles on large datasets. It's implemented in this Node library: https://github.com/bluesmoon/node-faststats Side note: I wish everyone would stop using the term Average to refer to the Arithmetic mean. "Average" just means some statistic used to summarize a dataset. It could be the Arithmetic Mea…

No we’re stuck with it because average was used colloquially for arithmetic mean for decades.

I wish people would stop bad-mouthing the arithmetic mean. If you have to convey information about a distribution and you’ve got only one number to do it, the arithmetic mean is for you.

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

#47

Post by [deleted] »

breuleux wrote: post #43
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

That's pretty neat! Can these be used to efficiently compute rolling percentiles (over windows of the data), or just incremental?

[deleted]

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

#48

Post by WireBaron »

breuleux wrote: post #43
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

That's pretty neat! Can these be used to efficiently compute rolling percentiles (over windows of the data), or just incremental?

The UDDSketch (default) implementation will allow rolling percentiles, though we still need a bit of work on our end to support it. There isn't a way to do this with TDigest however.

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

#49

Post by louisnow »

```To calculate the 10th percentile, let’s say we have 10,000 values. We take all of the values, order them from largest to smallest, and identify the 1001st value (where 1000 or 10% of the values are below it), which will be our 10th percentile.```

Isn't this contradictory? If we order the values from largest to smallest and take the 1001st value, then 10 % of the values are above/larger and not below/smaller. I believe it should say order from smallest to largest.

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

#50

Post by [deleted] »

hnuser123456 wrote: post #38

Gamers have an intuitive sense of this. Your average framerate can be arbitrarily high, but if you have a big stutter every second between the smooth moments, then a lower but more consistent framerate may be preferable, typically expressed as the 1% and 0.1% slowest frames, which at a relatively typical 100fps, represents the slowest frame every second and every 10 seconds.

[deleted]
Post reply on HN