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

151–160 of 173 posts

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

#151

Post by hoseja »

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…

>importance of graphing data before analyzing it

Very discouraging if one is trying to analyze data algorithmically. Often when faced with a problem in statistics, the answer is: "Look at the graph and use intuition!".

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

#153

Post by raxxorrax »

rendaw wrote: post #129
tantalor wrote: post #73

Earlier quoted context omitted.

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

That doesn't really make sense to me at all. Don't sort it, just have it?

Is the storage restriction the point?

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

#154

Post by barrenko »

tzs wrote: post #57
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.

I have no hope of finding a cite for this, but a long time ago I read some command line UI research that found if you had a system where commands ranged from instant to taking a small but noticeable time and you introduced delays in the faster commands to make it so all commands took the same small but noticeable time people would think that the system was now faster overall.

Presumably, also the reason we have those fake queue lines at airports (not sure the correct word is for it).

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

#155

Post by account42 »

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.

For games, one compounding factor is that you need to estimate how long the next frame will take in order to know how much time to simulate. If the variance is greater, the prediction will be worse leading the perceived game "speed" to vary from frame to frame.

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

#156

Post by williamdclt »

Cd00d wrote: post #146
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 "…

Did the candidate get an offer? Genuinely curious. I had a basic screening call fail once because the expected answer was (in my perspective) more naive than my answer. I'd love it if generating curiosity were an interview +1.

Whether they got it or not probably isn't useful information. Having a good/brilliant answer probably isn't the only point of the question, this probably wasn't the only question of the interview, and this probably wasn't the only interview

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

#157

Post by kazinator »

9935c101ab17a66 wrote: post #137
spiderice wrote: post #119

Earlier quoted context omitted.

> 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 be shocked if gamers didn't on average have a more intuitive sense of this than any of the groups you mentioned.

Yah, I don't think anyone's arguing that ONLY gamers will observe the phenomena, but I would be shocked if they weren't more sensitive to it than most groups.

"more sensitive" != "more intuitive"

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

#158

Post by djk447 »

jeremysalwen wrote: post #149
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

Not an expert on this topic but I noticed that the KLL algorithm (published in 2016) was not mentioned in this thread, which provides theoretically optimal performance for streaming quantiles with guaranteed worst case performance: http://courses.csail.mit.edu/6.854/20/sample-projects/B/stre... (And is pretty fast in practice).

NB: Post author here.

Interesting will have to take a look! Thanks for sharing!

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

#159

Post by djk447 »

jaygreco wrote: post #145

FYI, typo: > “In the below graph, half of the data is to the left (shaded in blue), and a half is to the right (shaded in purple), with the 50th percentile directly in the center.” But the half on the right is actually shaded yellow.

Thanks! Will get that fixed!

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

#160

Post by nancarrow »

abnry wrote: post #81

One way to think about why we tend to use averages instead of medians is that it is related to a really deep theorem in probability: The Central Limit Theorem. But I think we can twist our heads and see in a way that this is backwards. Mathematically, the mean is much easier to work with because it is linear and we can do algebra with it. That's how we got the Central Limit Theorem. Percentiles and the median, except…

It's more related to the law of large numbers than the CLT
Post reply on HN