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

71–80 of 173 posts

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

#71

Post by ilikebits »

Izikiel43 wrote: post #52
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 "…

> 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?

The real constraint here is probably "find the median of a huge data set without holding the entire data set in memory".

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

#72

Post by tantalor »

Izikiel43 wrote: post #52
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 "…

> 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?

No, for 2 reasons,

1. huge data set: heaps requires storing the whole set, but "huge" means "more than you can store"

2. without sorting it: heaps are basically semi-sorted, so you are breaking the rules

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

#73

Post by tantalor »

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

> Find the median ... randomly evict items

So, not find, but approximate. That's a different thing.

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

#74

Post by motohagiography »

Recovering product manager in me sees 90th percentile queries with outlier high latency and starts asking instead of how to reduce it, how we can to spin it out into a dedicated premium query feature, as if they're willing to wait, they're probably also willing to pay.

Highly recommend modelling your solution using queueing theory with this: https://queueing-tool.readthedocs.io/en/latest/

As an exercise in discovering the economics of how your platform works, even just thinking about it in these terms can save a great deal of time.

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

#75

Post by gpderetta »

groaner wrote: post #59
pachico wrote: post #46

Surprisingly, many software engineers I know never used percentiles and keep using mean average. True story.

Not surprising, because computing mean is O(n) and median is O(n log n). Lack of resources or pure laziness doesn't make it the right measure to use though.

Introselect is O(n), right?

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

#76

Post by mschuetz »

pachico wrote: post #46

Surprisingly, many software engineers I know never used percentiles and keep using mean average. True story.

The mean is something you can easily compute progressively and with trivial resources. Median and percentiles, on the other hand, can be super expensive and potentially unsuitable for some real-time applications, since you need to maintain a sorted list of all relevant samples.

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

#77

Post by hnuser123456 »

kazinator wrote: post #64
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.

Gamers do not have a more intuitive sense for this than movie watchers, video/voice talkers, not to mention users who type text into bloated web browsers or lagged remote login sessions. I would rather have a rock-steady consistent 500 ms reponse time when typing text, than to have a 100 ms average response time which randomly spikes to outliers that go past one second. A rock-steady, though poor, event rate in a pai…

Maybe not all, but ones who create and consume analysis like this

https://www.techpowerup.com/review/msi-geforce-rtx-3090-gami...

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

#78

Post by djk447 »

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

NB: Post author here. Oops, yep, that should probably be order from smallest to largest. Thanks for the correction!

Fixed!

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

#79

Post by djk447 »

aidenn0 wrote: post #66

Be careful translating percentiles of requests to percentiles of users; if less than 10% of your requests take over 1 second, but a typical user makes 10 requests, it's possible that the majority your users are seeing a request take over 1 second.

NB: Post author here.

Yep! Briefly noted that in the post, but deserves re-stating! it's definitely a more complex analysis to figure out the percentage of users affected (though often more important) could be majority could also be one user who has some data scientist programmatically making hundreds of long API calls for some task...(can you tell that I ran into that? Even worse it was one of our own data scientists ;) ).

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

#80

Post by jeffbee »

WireBaron wrote: post #48
breuleux wrote: post #43

Earlier quoted context omitted.

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.

Sure there is. You simply maintain N phases of digests, and every T time you evict a phase and recompute the summary (because T-digests are easily merged).
Post reply on HN