1
$\begingroup$

I'm trying to estimate quantiles from cumulative distribution functions. Given N CDFs are there techniques that can be used to merge them to form another CDF from which a quantile can be estimated ?

Thanks everyone for looking at the question. Here is a more concrete example: Imagine a web service being served by N server instances. Each server constructs an empirical CDF of the response times of a request. Now I would like to aggregate or merge the CDFs to find say the 95th percentile response time of the web service. The only data available is the empirical CDF and number of samples used to construct the CDF.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "merging" CDF's? This is probably straightforward if you specify what operation you are performing on the N random variables with those N CDF's and how those random variables are related to each other. $\endgroup$ – caburke Jun 14 '13 at 15:42
3
$\begingroup$

This depends on exactly what you are holding.

If you are holding the entire set of cumulative probabilities, you must be holding the data too to expect to do anything with them. (If I tell you that I have cumulative probabilities 0.25, 0.5, 0.75, 1 I am not telling you anything much.) So the answer is then that you can, but you must combine the data end-to-end and recompute the quantiles.

Conversely, if you are holding some approximation, then you have to explain what you are holding and what you expect to do with it.

$\endgroup$
2
$\begingroup$

If I understand you correctly, your question can be answered by using a data structure to estimate quantiles - one for each server instance, and that these N data structures has the ability to be 'merged' (or 'reduced') with the rest to get aggregate estimates of the entire cluster.

I believe the TDigest data structure should be able to help you: https://github.com/tdunning/t-digest

Here is the description:

A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means. The t-digest algorithm is also very parallel friendly making it useful in map-reduce and parallel streaming applications.

This way, you can calculate estimates for each server, AND, also combine these aggregated estimates for the entire cluster, without processing ALL the raw data for the entire cluster again.

More details on the underlying techniques can be followed from the link. I believe it is based on the q-digest algorithm.

$\endgroup$
1
$\begingroup$

If I were asking this question I would mean this: If I have some number of empirical CDF's, but not the raw data that generated them, and I want to make what would the CDF have been from the entire aggregate of the data, how would I go about doing it.

My approach would be: Regenerate the data from the CDF's, and knowledge of how many elements were in each subset of my intended set. If I knew that I had 100 elements in an individual set, then I would determine a set of 100 elements such that they would generate that element CDF. I would iterate this over all sub-CDF to compose an equivalent total data, then compute the CDF on it.

If you don't know the relative memberships of the sub-CDF's then this doesn't work.

Questions:

  • What are the unknowns?
  • What are the knowns?
  • What application do you want to apply this answer to?

EDIT:

If you record the total number of requests at the server then the following might work:

for each server
    for each value in the eCDF starting at lowest frequency and moving up
          compute the number of times that value happened
              multiply minimum frequency by totalrequests(server)
              pass that as output number and the domain value as that number as outputs
              subtract that number from all future estimates
          append that number of duplicates to variable "biglist"
    end
end

compute eCDF of biglist
find value at desired percentile value

This will work. It is not necessarily compute-time optimal, but in general computers are insanely fast so being clear and easy to program/debug could be measure of goodness.

For example, if you have CDF frequencies of [0.2 0.4 0.6 0.8, 1.0] for domain values of [0, 2, 3, 4, 6] and know that there were only 5 samples, you would determine the "outputs" to append to "biglist" as follows:

first pass through loop:
pop the lowest number off the list: 0.2
multiply by the count: 0.2 * 5 = 1
you pass "1" and "0" as outputs so that one occurrence of 0 is appended to biglist
you subtract 1 from all future passed values

second pass through loop:
pop the lowest number off the list: 0.4
multiply by the count: 0.4* 5 = 2
subtract the offset from it: 2 - 1 = 1
pass that count and the domain to be appended to biglist
you now subtract 2 from all future passed values

At this point your biglist contains [0, 2].

third pass through loop:
pop the lowest number off: 0.6
mult by count: 0.6*5 = 3
subtract the offset from it: 3 - 2 = 1
pass outputs for biglist: [1]
add this count to the offset: 2 + 1 = 3
et cetera.

By inspection you can see that in the center this looks like a top-hat and at the edges there are more triangular distributions.

At the end you have a list of [0 2 3 4 6] from which to make an empirical CDF. You now go to your next sub-eCDF and process similarly to append to this list. After having processed all lists, you then make your overall eCDF.

$\endgroup$
  • $\begingroup$ Thanks everyone for looking at the question. Here is a more concrete example: Imagine a web service being served by N server instances. Each server constructs a CDF of the response times of a request. Now I would like to aggregate or merge the CDFs to find say the 95th percentile response time of the web service. $\endgroup$ – stareye Jun 14 '13 at 17:16
  • $\begingroup$ Thanks for the edit, Nick. I can be a terrible speeler. $\endgroup$ – EngrStudent - Reinstate Monica Jun 15 '13 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.