3
$\begingroup$

Let's say we have sets $X=\{x_1, x_2, \ldots, x_m\}, Y=\{y_1, y_2, \ldots, y_n\}$ and we have some estimate (or exact) quantile information about them at some level $a$. How could we approximate the quantiles at that same level $a$ for the union of the sets $X\cup Y$, without assuming that they come from the same distribution?

If impossible, what if we relax those assumptions and assume they do come from the same distribution? In other words, how could we calculate quantiles for an extremely large dataset with a sequence of parallel computations on subsets?

edit: I found this: Estimate population quantiles from subpopulations' quantiles, which was helpful - any other thoughts? In particular, how would one parallelize the computation of quantiles?

edit: To be more precise, I'm interested in computing an estimate and confidence interval for the $p$-th quantile of a large dataset by computing the quantiles on subsamples of that dataset in parallel. Let's say that it would be acceptable to assume that the subsamples are randomly sampled from the larger dataset, if that makes the problem more tractable.

$\endgroup$
  • $\begingroup$ Have a look at this: engr.uconn.edu/~rajasek/Cdm1.pdf sems relevant. $\endgroup$ – kjetil b halvorsen Sep 9 '15 at 20:06
  • $\begingroup$ These are two different problems. If you want to obtain the p-th quantile of a large sample exact;y using many parallel computations on subsets, then this can be done. There are many c++ implementations of parallel versions of nth_element, here is a link to the first one google gave me. This approach has complexity~ O(N/p) where N is the length of your extremely large data set and p is the number of parallel machines you are using.... $\endgroup$ – user603 Sep 9 '15 at 20:31
  • $\begingroup$ ...It i also possible to estimate (and get a confidence interval for) the p-th quantile of the very large data set using sub-samples of it (this is a simple application of the bootstrap), which is an embarrassingly parallel problem (you can compute the quantiles on the sub-samples in parallel). However, in this case you would need to assume that the subsets are a random sample of the very large dataset. Make your question more precise by eliciting which approach you are interested in. $\endgroup$ – user603 Sep 9 '15 at 20:38
  • 2
    $\begingroup$ I'm interested in the latter (your second comment). Sorry for the impreciseness; see edit. $\endgroup$ – bayesian Sep 9 '15 at 23:55
1
$\begingroup$

I suppose you deal with a data vector of length $n$ where $n$ is so large that it becomes necessary to spread the computations over many machines and that this vector cannot fit inside the memory of any single one of those machines. This squares neatly with the definition of big data as defined here.

Suppose that the dataset $\{X_i\}_{i=1}^n$ is composed of independent draws from a distribution $F$ and denote $q(\alpha)$ the $\alpha$ quantile of $F$. Throughout, I will assume that $F$ is differentiable at $q(\alpha)$ and that $F^\prime(q(\alpha))>0$.

The sample estimator of $q(\alpha)$ is $\hat{q}_n(\alpha)$ and is defined as the minimizer over $t\in\mathbb{R}$ of:

$$(0)\quad h_n(t)=\sum_{i=1}^n\rho_\alpha(X_i-t).$$

where $\rho_{\alpha}(u)=|u(\alpha-\mathbb{I}_{(u<0)})|$ and $\mathbb{I}$ is the indicator variable [0].

Assume that the dataset $\{X_i\}_{i=1}^n$ is partitioned into $k$ non-overlapping sub-samples of lengths $\{m_j\}_{j=1}^k$. I will denote $\{\hat{q}_n^{j}(\alpha)\}_{j=1}^k$ the estimators of $\hat{q}_n(\alpha)$ obtained by solving (0) on the respective sub-samples. Then, if:

$$\min_{j=1}^k\lim_{n\to\infty} \frac{m_j}{n}>0$$ the estimator:

$$\bar{q}_n(\alpha)=\sum_{j=1}^k\frac{m_j}{n}\hat{q}_n^{j}(\alpha)$$

satisfies:

$$\sqrt{n}(\bar{q}_n(\alpha)-\hat{q}_n(\alpha))=o_p(1).$$

(You can find more details of these computations including the asymptotic variances of $\bar{q}_n(\alpha)$ in [1]).

Therefore, letting $m_j=m\;\forall j$, you can use non overlapping sub-samples of your original data set to get a computationally convenient estimate of $\hat{q}_n(\alpha)$. Given $p$ computing units, this divide and conquer strategy will have cost $O(km/p)$ and storage $O(km)$ (versus $O(n)$ and $O(n)$ for computing (0) directly) at an asymptotically negligible cost in terms of precision. The finite sample costs will depend on how small $F^\prime(\alpha)$ is, but will typically be acceptable as soon as $m\geq 2^7$ to $m\geq 2^6$.

Compared to running the parallel version of $\texttt{nth_element}$ I linked to in my comment above, the implementation based on sub-samples will be simpler (and also scale much better as $p$ becomes larger than the number of cores on a single computing machine). Another advantage of the approach based on sub-samples over the one based on the parallel version of $\texttt{nth_element}$ is that the $O(km)$-space complexity can be split across the memory of multiple machines, even if $O(n)$ cannot fit inside the memory of any single one of them.

On the minus side, the solution based on $\bar{q}_n(\alpha)$ will not be permutation invariant (changing the order of the observation will give a different result).

  • [0]. Koencker, R. Quantile regression.
  • [1]. Knight, K. and Bassett, J.W. Second order improvements of sample quantiles using subsamples
$\endgroup$
  • 1
    $\begingroup$ Thanks! Is it true that $km = n$? so the storage is the same? Whereas cost will be amortized over $p$ computing units? Essentially, you're saying we can divide the dataset into $p$ parts, calculate the median of each, and then take the average, with asymptotically negligible cost, assuming that the dataset is composed of independent draws from the same distribution? $\endgroup$ – bayesian Sep 14 '15 at 20:30
  • $\begingroup$ Yes. You can use simulations to show that, for example for alpha=0.95, even for a very skewed distribution (weibull with shape=1), increasing $m$ beyond $2^6$ to $2^7$ does not much improve the results. The cut-off value for $m$ is inversely proportional to $F^\prime(\alpha)$. $\endgroup$ – user603 Sep 14 '15 at 22:28

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.