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

161–170 of 173 posts

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

#161

Post by _0ffh »

djk447 wrote: post #23
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

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

Hi, in an unrelated nitpick: The relative error should be calculated by dividing the error by the true value, not by it's approximation. Still, very nice writeup!

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

#163

Post by djk447 »

_0ffh wrote: post #161
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

Hi, in an unrelated nitpick: The relative error should be calculated by dividing the error by the true value, not by it's approximation. Still, very nice writeup!

Thanks! messed up the formula but had it right in the text :( Fixed now.

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

#164

Post by LoriP »

louisnow wrote: post #49

```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 bel…

Thanks, we corrected this quite quickly. Appreciated!

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

#166

Post by datavirtue »

Can someone bake this down to a sentence? I think I understand what they are saying since I have been faced with using these metrics and in having been tempted to use average response times I recognized that average is not a good baseline since it moves in relation to the outliers (which are usually the problem requests and there can be many or few).

How do you calculate these percentiles and use them as a trigger for alerts?

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

#167

Post by [deleted] »

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 "…

[deleted]

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

#168

Post by rogers18445 »

mfreed wrote: post #55
vvern wrote: post #40

Earlier quoted context omitted.

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

If folks are interested: https://github.com/timescale/timescaledb-toolkit/blob/main/e... (The TimescaleDB Toolkit is also implemented in Rust)

Facebook seems to have an even better performance implementation using sqrt. Might make sense to port that over to Rust. https://github.com/facebook/folly/blob/master/folly/stats/TD...

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

#169

Post by panda88888 »

raxxorrax wrote: post #153
rendaw wrote: post #129

Earlier quoted context omitted.

> without sorting it... have a fixed size sorted buffer (that you sort yourself)

That doesn't really make sense to me at all. Don't sort it, just have it? Is the storage restriction the point?

Yes. The goal is to find (or approximate) the median without storing all the elements. Instead, it approximates the median by finding the median of randomly selected samples from the elements.

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

#170

Post by eric-hu »

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.

There was a “Latency” multiplayer setting in Starcraft 1. I think it was there precisely to give players control over smoothness of network latency instead of graphics and processing latency. I think this just adds yet another example of your observation.
Post reply on HN