How percentile approximation works and why it's more useful than averages • Hacker News Board

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

#61

Post by 5faulker » Tue, Sep 14, 2021, 6:38 PM UTC

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?

It's funny that this is often left out from a data & algorithm class.

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

#62

Post by slaymaker1907 » Tue, Sep 14, 2021, 6:42 PM UTC

doctorsher wrote: post #19

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

I assume most of the distributions a marketing department would be dealing with are generally normal in which case stddev is a great way to analyze the data. This can be easily verified by just plotting said data and making sure the tails don't look weird.

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

#63

Post by satvikpendem » Tue, Sep 14, 2021, 6:45 PM UTC

I often see HN articles crop up soon after a related post, in this case this Ask HN poster [0] being driven crazy by people averaging percentiles and them not seeing that it's a big deal. It's pretty funny to see such tuples of posts appearing.

https://news.ycombinator.com/item?id=28518795

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

#64

Post by kazinator » Tue, Sep 14, 2021, 6:47 PM UTC

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 paint application is better for drawing a freehand curve (especially if the program interpolates well) than a really fast rate that suddenly has a glitch in it, spoiling your work.

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

#65

Post by ruchin_k » Tue, Sep 14, 2021, 6:47 PM UTC

Spent several years in venture capital investing and averages were always misleading - as Nassim Taleb says "Never cross a river that is on average 4 feet deep"

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

#66

Post by aidenn0 » Tue, Sep 14, 2021, 6:48 PM UTC

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.

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

#67

Post by fotta » Tue, Sep 14, 2021, 6:49 PM UTC

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

yep I had to implement t-digest in a monitoring library. another alternative (although older) that the prometheus libraries use is CKMS quantiles [0].

[0] http://dimacs.rutgers.edu/~graham/pubs/papers/bquant-icde.pd...

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

#68

Post by 123pie123 » Tue, Sep 14, 2021, 6:50 PM UTC

I had to explain the data usage of an interface that looked extremely busy from the standard graphs

I did a percentile graph of the usage - the data was only typically using 5% of the maximum throughput, no-one could really understand the graph though

so I did a zoomed-in version of the normal data usage graph and it looked like a blip lasting 1/20 of the time - everyone got that - eg it was peaking every few seconds and then doing nothing for ages

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

#69

Post by robbrown451 » Tue, Sep 14, 2021, 6:53 PM UTC

ruchin_k wrote: post #65

Spent several years in venture capital investing and averages were always misleading - as Nassim Taleb says "Never cross a river that is on average 4 feet deep"

Median/50 percentile isn't a whole lot better in that case.

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

#70

Post by slaymaker1907 » Tue, Sep 14, 2021, 6:54 PM UTC

mherdeg wrote: post #58

I've skimmed some of the literature here when I've spent time trying to help people with their bucket boundaries for Prometheus-style instrumentation of things denominated in "seconds", such as processing time and freshness. My use case is a little different from what's described here or in a lot of the literature. Some of the differences: (1) You have to pre-decide on bucket values, often hardcoded or stored in code…

One thing you could try to use are variance optimal histograms. These are histograms which set bucket boundaries such that the weighted average variance in the buckets is minimized. Unfortunately, this algorithm is quadratic with the number of data points, but you could try approximating the optimum by taking random subsets of the data, computing the histogram, then seeing how well the histogram does on the whole dataset.

http://www.mathcs.emory.edu/~cheung/Courses/584/Syllabus/pap...