<p>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 &gt; 0$, which means that if your true marker is (say) $5\%$, and $\epsilon = 0.01$, your true marker will be between $4-6\%$. <a href="http://www.cs.ucsb.edu/~suri/psdir/ency.pdf" rel="nofollow">There's a nice survey of results here</a>. </p>

<p>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. </p>

CC BY-SA 3.0
2013-08-24T16:20:45.060Z
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?
László
CC BY-SA 3.0
2013-08-24T16:41:41.213Z
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)
Suresh Venkat
CC BY-SA 3.0
2013-08-24T16:42:53.460Z
Excellent, thanks, that's what I thought.
László
CC BY-SA 3.0
2013-08-24T16:53:03.507Z
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} )$?
László
CC BY-SA 3.0
2013-08-24T16:56:04.430Z
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$.
Suresh Venkat
CC BY-SA 3.0
2013-08-25T11:55:49.777Z
Another concern (though $\Theta$ still unresolved) is that to cut the data into 20 bins, I will take 19 vingtiles. Any of those being wrong must a have much higher probability than a single one being wrong. Though as the vingtiles are highly correlated, perhaps not that much? (I.e. if I happened to oversample observations in the 3rd population percentile, all quantiles will be too high?)
László
CC BY-SA 3.0
2013-08-25T17:30:20.547Z
I am even more confused now. I check some other literature, and page 3 [here](http://infolab.stanford.edu/~manku/papers/04pods-sliding.pdf) seems to refer to the same formula, again without an exact reference but it being "well-known," while the formula differs by an extra $\varepsilon$ term and thus leads to larger samples.
László
CC BY-SA 3.0
2013-08-25T18:55:05.030Z
I think $\Theta$ is simply [this](http://stackoverflow.com/a/10376776/938408), so no specific guidance on how to pick the sample size. As it should depend on the density. Sigh.
László
CC BY-SA 3.0
2013-08-25T19:54:13.437Z
No no. The $\phi$ you refer to comes from the reference [5], and is the $\phi n$ quantile (the bound is for estimating only the $\phi$-quantiles. For example, if you want the deciles, then $\phi = 0.1$.
Suresh Venkat
CC BY-SA 3.0
2013-08-26T15:46:15.373Z
Thanks again. I am not sure where I referred to $\phi$. In any case, as the downsampling itself was more of a statistics question, I had a sister question on CrossValidate. Perhaps you can check whether the [answer](http://stats.stackexchange.com/a/68308/6534) I came up with in the end over there is sensible.
László
CC BY-SA 3.0
2013-08-24T16:10:43.567Z
2013-08-25T06:26:35.130Z
2013-08-25T06:26:35.130Z
Suresh Venkat
<p>It is possible to find the quantiles in $O(N)$ using a straightforward modification of the selection algorithm based on quicksort (see <a href="http://en.wikipedia.org/wiki/Selection_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Selection_algorithm</a>). </p>

CC BY-SA 3.0
2013-08-24T15:46:38.120Z
2013-08-24T15:46:38.120Z
siravan
<p>What is the state-of-the art on algorithms that calculate/estimate approximate quantiles?</p>

<p>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%.</p>

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

CC BY-SA 3.0
2013-08-25T06:11:38.013Z
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.
CC BY-SA 3.0
2013-08-25T11:38:57.837Z
@D.W. All $N$ values are stored in memory and we can freely access them.
László
CC BY-SA 3.0
2013-08-25T18:40:23.143Z
Hi László, thanks for your response.  I suggest you edit the question to make this clear in the question.
D.W.
CC BY-SA 3.0
2013-08-26T15:45:11.027Z
@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](http://stats.stackexchange.com/a/68308/6534) I came up with in the end over there is sensible.
László
<approximation-algorithms><sorting><sample-complexity>
algorithms to split data into roughly equal sized quantiles
László
# algorithms to split data into roughly equal sized quantiles

(Asked by: username_0 on 2013-08-24)

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

**Tags:** approximation-algorithms, sorting, sample-complexity

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1 All $N$ values are stored in memory and we can freely access them.  
> **username_1**: Hi username_0, thanks for your response.  I suggest you edit the question to make this clear in the question.  
> **username_0**: @username_1 As the downsampling itself was more of a statistics question, I had a sister question on CrossValidate. Perhaps you can check whether the [answer](http://stats.stackexchange.com/a/68308/6534) I came up with in the end over there is sensible.  

---

## 2 answers

### Answer by username_2 on 2013-08-24. Score: 3

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](http://www.cs.ucsb.edu/~suri/psdir/ency.pdf).

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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)  
> **username_0**: Excellent, thanks, that's what I thought.  
> **username_0**: 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} )$?  
> **username_2**: 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$.  
> **username_0**: Another concern (though $\Theta$ still unresolved) is that to cut the data into 20 bins, I will take 19 vingtiles. Any of those being wrong must a have much higher probability than a single one being wrong. Though as the vingtiles are highly correlated, perhaps not that much? (I.e. if I happened to oversample observations in the 3rd population percentile, all quantiles will be too high?)  
> **username_0**: I am even more confused now. I check some other literature, and page 3 [here](http://infolab.stanford.edu/~manku/papers/04pods-sliding.pdf) seems to refer to the same formula, again without an exact reference but it being "well-known," while the formula differs by an extra $\varepsilon$ term and thus leads to larger samples.  
> **username_0**: I think $\Theta$ is simply [this](http://stackoverflow.com/a/10376776/938408), so no specific guidance on how to pick the sample size. As it should depend on the density. Sigh.  
> **username_2**: No no. The $\phi$ you refer to comes from the reference [5], and is the $\phi n$ quantile (the bound is for estimating only the $\phi$-quantiles. For example, if you want the deciles, then $\phi = 0.1$.  
> **username_0**: Thanks again. I am not sure where I referred to $\phi$. In any case, as the downsampling itself was more of a statistics question, I had a sister question on CrossValidate. Perhaps you can check whether the [answer](http://stats.stackexchange.com/a/68308/6534) I came up with in the end over there is sensible.  

---

### Answer by username_3 on 2013-08-24. Score: 3

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


---

