1
$\begingroup$

What is the state-of-the art on algorithms that calculate/estimate approximate quantiles?

I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having roughly equal sized bins. E.g. if I need vingtiles, I want to have low risk of having any bin having less than 4% of the data or more than 6%.

If I need to implement this in an existing high-level statistical system, I think the question inevitable becomes restricted to downsampling from a population of $N$ to a subsample of $n$ and take quantiles using sorting at costs at the order $O(n \log n)$ instead of $O(N \log N)$, but at the right ratio as a function of the original sample size. I am looking for guidance on how to pick $n$ for any $N$.

$\endgroup$
4
  • $\begingroup$ Are you looking for a streaming (online) algorithm (where you must process each value as it appears, and can only keep $O(1)$ state, so you cannot remember all values)? Or are you assuming that all $N$ values are stored in memory and we can freely access them? $\endgroup$
    – D.W.
    Aug 25, 2013 at 6:11
  • $\begingroup$ @D.W. All $N$ values are stored in memory and we can freely access them. $\endgroup$
    – László
    Aug 25, 2013 at 11:38
  • $\begingroup$ Hi László, thanks for your response. I suggest you edit the question to make this clear in the question. $\endgroup$
    – D.W.
    Aug 25, 2013 at 18:40
  • $\begingroup$ @D.W. As the downsampling itself was more of a statistics question, I had a sister question on CrossValidate. Perhaps you can check whether the answer I came up with in the end over there is sensible. $\endgroup$
    – László
    Aug 26, 2013 at 15:45

2 Answers 2

3
$\begingroup$

It is possible to find the quantiles in $O(N)$ using a straightforward modification of the selection algorithm based on quicksort (see http://en.wikipedia.org/wiki/Selection_algorithm).

$\endgroup$
3
$\begingroup$

One line of attack on approximate quantiles is via streaming algorithms. In one scan of the data (i.e., very efficiently) you can get estimates for the quantiles within error $\epsilon N$ for any $\epsilon > 0$, which means that if your true marker is (say) $5\%$, and $\epsilon = 0.01$, your true marker will be between $4-6\%$. There's a nice survey of results here.

But streaming algorithms are potentially overkill. You can also sample the data to get approximate counts. Roughly speaking, if you need an error of at most $\epsilon N$ in the absolute estimate, then you need a sample of size $n = O(\frac{1}{\epsilon^2}\log \frac{1}{\epsilon})$ with reasonably high probability.

$\endgroup$
10
  • $\begingroup$ Thanks, some limitations of the environment where I need to implement this might be an extra reason to stick to the second suggestion. But to be sure, you suggest a sample of 20,000 for (max) percentage point errors in the quantile, irrespective of the quantile or the size of the population N? I might be confused by your use of $n$ in $\varepsilon n$ where I used n for the subsample. Also, you I am not sure what you mean by me having a sample of some size "with reasonably high probability." The sample size can be deterministic, no? $\endgroup$
    – László
    Aug 24, 2013 at 16:20
  • $\begingroup$ ah. my "n" is the population size (your "N"). And the "high probability bound" refers to the chance that the sample has the desired properties (i.e there's a chance that the sample will have terrible approximation quality) $\endgroup$ Aug 24, 2013 at 16:41
  • $\begingroup$ Excellent, thanks, that's what I thought. $\endgroup$
    – László
    Aug 24, 2013 at 16:42
  • $\begingroup$ I must be reading the survey wrong. What is $\Theta$ suddenly in their formula on the top of page 3? A sample of size $\Theta ( \frac{1}{\varepsilon^2} \log \frac{1}{\delta} )$? $\endgroup$
    – László
    Aug 24, 2013 at 16:53
  • $\begingroup$ Yes, I was wondering about that myself. I think there's a mistake there. Typically, the $\Theta$ shows up when you're trying to preserves quantiles of the form $\Theta n$. $\endgroup$ Aug 24, 2013 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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