algorithms to split data into roughly equal sized quantiles

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

• 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?
– D.W.
Aug 25 '13 at 6:11
• @D.W. All $N$ values are stored in memory and we can freely access them. Aug 25 '13 at 11:38
• Hi László, thanks for your response. I suggest you edit the question to make this clear in the question.
– D.W.
Aug 25 '13 at 18:40
• @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. Aug 26 '13 at 15:45

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).
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.
• 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? Aug 24 '13 at 16:20
• 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} )$? Aug 24 '13 at 16:53
• 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$. Aug 24 '13 at 16:56