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

81–90 of 173 posts

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

#81

Post by abnry »

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 for symmetric distributions, are not as easy to work with. They involve solving for the inverse of the cumulative function.

But in many ways, the median and percentiles are a more relevant and intuitive number to think about. Especially in contexts where linearity is inappropriate!

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

#82

Post by wruza »

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.

I guess that’s because our minds (and animal minds as well) are always aware of the pace of repetitive events. If something is off, the anxiety alarm rings. One old book on the brain machinery described an example of a cat that was relaxing near the metronome and became alert when it was suddenly stopped. Unpredictable delays are disturbing, because a mispredicted event means you may be in a dangerous situation and have to recalibrate now.

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

#84

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

#86

Post by riskneutral »

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

Also relevant: Single-Pass Online Statistics Algorithms

[1] http://www.numericalexpert.com/articles/single_pass_stat/

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

#87

Post by djk447 »

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…

NB: Post author here.

This is interesting and I totally get at least some of the problems you're facing. I wonder if you could take some of the strategies from t-digest and modify a bit to accomplish...I'd be interested in seeing some sort of implementation of this and would love to see if we can get it into our toolkit if you do...or you can also open up a ticket for us and we'll see if we can prioritize to work on something like it ourselves.

I do think there are some interesting ways you can cut corners if you know things about the "SLO" or other sort of cutoff values, but I'd have to think more deeply about it to say more. Essentially we want a variable error rate based on the distance away from a known value, where you have little error in the values relatively close to the known value, care little if at all for fine distinctions on the low end and, once you get past some high end value you could probably bucket everything above it into a "large outliers" bucket or something too...meaning you p999 could get out of hand if you start getting lots of stuff above a threshold, but, if that starts happening, probably everything's already burning down, so might not be that useful to know it's burning down in a very specific way...

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

#88

Post by 10000truths »

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.

If you're going to use multiple quantities to summarize a distribution, wouldn't using percentiles for all of them give you the most information? The mean and standard deviation could then be estimated from that data.

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

#89

Post by djk447 »

jeffbee wrote: post #80
WireBaron wrote: post #48

Earlier quoted context omitted.

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

I think this would be a tumbling window rather than a true "rolling" tdigest. I suppose you could decrement the buckets, but it gets a little weird as splits can't really be unsplit. The tumbling window one would probably work, though Tdigest is a little weird on merge etc as it's not completely deterministic with respect to ordering and merging (Uddsketch is) so it's likely you get something that is more than good enough, but wouldn't be the same as if you just calculated it directly so it gets a little confusing and difficult.

(NB: Post author here).

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

#90

Post by xyzzyz »

tantalor wrote: post #72
Izikiel43 wrote: post #52

Earlier quoted context omitted.

> 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

You can actually construct the heap from unsorted data in O(n) time, so constructing the heap is definitely not sorting. However, yeah, to actually use the heap to find median in O(n) time, you need to do something similar to magic-five (median of medians) algorithm.
Post reply on HN