Percentiles derived from percentiles

[Baron Schwartz]

Imagine that I observe some high-frequency stream of events, such as requests to a server. Let's say that there are 20000 per second, and once per second I compute the 95th percentile over the second. I discard everything else and only retain this once-per-second summary statistic as a time-series metric.

Now I want to obtain percentiles over 1-minute, 5-minute, and 1-hour intervals, based on the 95th percentile metric I've stored.  In other words, I want to derive the 95th percentile of the original stream of events, at coarser granularity.  My intuition (that 9-letter word again) says this is possible. Fear of intuition says the results might be invalid. What does The Mailing List say?

[Greg Hunt]

The problem is sensitive to the order of the observations. Consider the 75th percentile of three hypothetical sampling intervals:

(1,1,1,1) is 1, (1,1,5,5) is 5, (1,1,5,5) is 5

The same samples rearranged give a different set of percentiles:

(1,1,1,1) is 1, (1,1,1,1) is 1, (5,5,5,5) is 5.

The overall 75th is unchanged but the percentiles over the shorter intervals are quite different. If there is an algorithm it needs to somehow aggregate 1 and 1 and 5 to the same value as it aggregates 1 and 5 and 5. 

Of course then the sequences (1,1,1,1) and (1,1,1,1) and (1,1,5,5) have the same individual percentiles (1,1,5) but a different overall 75th (1).

Am I missing something? The same set of individual same interval percentile values can relate to some number of different overall percentile values.

I suspect that if the samples were all drawn from a known and reasonably simple distribution that you could infer the value with a defined degree of certainty if there were enough data points, but that seems like a long shot if it is the usual system data with multiple things going on behind the set of numbers.

Greg

On Friday, May 10, 2013, Baron Schwartz wrote:

Imagine that I observe some high-frequency stream of events, such as requests to a server. Let's say that there are 20000 per second, and once per second I compute the 95th percentile over the second. I discard everything else and only retain this once-per-second summary statistic as a time-series metric.

Now I want to obtain percentiles over 1-minute, 5-minute, and 1-hour intervals, based on the 95th percentile metric I've stored.  In other words, I want to derive the 95th percentile of the original stream of events, at coarser granularity.  My intuition (that 9-letter word again) says this is possible. Fear of intuition says the results might be invalid. What does The Mailing List say?

--
You received this message because you are subscribed to the Google Groups "Guerrilla Capacity Planning" group.
To unsubscribe from this group and stop receiving emails from it, send an email to guerrilla-capacity-...@googlegroups.com.
To post to this group, send email to guerrilla-cap...@googlegroups.com.
Visit this group at http://groups.google.com/group/guerrilla-capacity-planning?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Paul Puglia]

90th %-tile of what?  Service time? Response time?

Sent from my iPhone

On May 9, 2013, at 2:04 PM, Baron Schwartz <baron.s...@gmail.com> wrote:

Imagine that I observe some high-frequency stream of events, such as requests to a server. Let's say that there are 20000 per second, and once per second I compute the 95th percentile over the second. I discard everything else and only retain this once-per-second summary statistic as a time-series metric.

Now I want to obtain percentiles over 1-minute, 5-minute, and 1-hour intervals, based on the 95th percentile metric I've stored.  In other words, I want to derive the 95th percentile of the original stream of events, at coarser granularity.  My intuition (that 9-letter word again) says this is possible. Fear of intuition says the results might be invalid. What does The Mailing List say?

--

[Uriel Carrasquilla]

I have struggled with this issue for a long time.

I have tackled this problem with two very different approaches.

1) when the data was manageable and I could keep all the details for a month.

I ended up keeping all the records and reported percentiles per hour, per day and per month.

The problem is that the number of records can become serious and sorting every time the sample gets larger seems like a waste of resources.

2) Extremely large amounts of data required a new approach

What I do now is keep weighted averages.

For example, if the interval has 10 values, I keep the average and the count.

Then, as I merge different mutually exclusive intervals I end up with a new weighted average with a new number of records.

That way I can summarize going forward.

The problem is that I don't have my peaks, or any idea of the distribution.

If the data was to be parametric, there would be an easy solution.  You may want to test your data.

So I started keeping the maximum observed per sample period (it could be a percentile such as the 95th).

I do it in a way that my intervals are one hour so I get to keep my busiest one hour (the 95th percentile observed in every hour where I keep the maximum 95th from hour to hour).

As I work with different intervals, I keep on selecting my higher value.

I haven't told my math professor because I am afraid he may send me back to elementary school.

I am very curious to find out what might be an acceptable solution.

Uriel

---

From: guerrilla-cap...@googlegroups.com [guerrilla-cap...@googlegroups.com] on behalf of Baron Schwartz [baron.s...@gmail.com]
Sent: Thursday, May 09, 2013 2:04 PM
To: guerrilla-cap...@googlegroups.com
Subject: Percentiles derived from percentiles

Imagine that I observe some high-frequency stream of events, such as requests to a server. Let's say that there are 20000 per second, and once per second I compute the 95th percentile over the second. I discard everything else and only retain this once-per-second summary statistic as a time-series metric.

Now I want to obtain percentiles over 1-minute, 5-minute, and 1-hour intervals, based on the 95th percentile metric I've stored.  In other words, I want to derive the 95th percentile of the original stream of events, at coarser granularity.  My intuition (that 9-letter word again) says this is possible. Fear of intuition says the results might be invalid. What does The Mailing List say?

--

[Uriel Carrasquilla]

in my case "RTT".

---

From: guerrilla-cap...@googlegroups.com [guerrilla-cap...@googlegroups.com] on behalf of Paul Puglia [pjpu...@earthlink.net]
Sent: Friday, May 10, 2013 2:21 PM
To: guerrilla-cap...@googlegroups.com
Subject: Re: Percentiles derived from percentiles

[Greg Hunt]

If the range is stable you can summarise each interval into bins (a histogram) and the sets of bins can be summed to get to the longer intervals.  Percentiles can then be interpolated with a loss of accuracy that depends on the bin width and the shape of the distribution.