# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
```
0: Data stream \(S\), quantile \(q\), \(O(1)\) units of memory
0: estimated quantile value \(\tilde{m}\) \(mode=0\)\(\triangleright\) mode of operation: \(MAX\_MIN=1\), \(AVERAGE=2\) \(\tilde{m}=0\) \(max=-\infty\) \(min=+\infty\) \(sum=0\) \(count=0\) \(countLow=0\) \(countHigh=0\) \(\lambda=0\) \(count=0\) \(threshold=0\) \(toggleThreshold=0.7\) if\(q>toggleThreshold\)then \(mode=1\) else \(mode=2\) endif for each\(s_{i}\in S\)do \(count=count+1\) if\(count\leq 1\)then \(\tilde{m}=s_{i}\)  continue \(\triangleright\) go to the next iteration endif \(threshold=count\times quantile\) if\(s_{i}<min\)then \(min=s_{i}\) endif if\(s_{i}>max\)then \(max=s_{i}\) endif \(sum=sum+s_{i}\) if\(mode==1\)then \(\lambda=\frac{max-min}{count}\) else \(\lambda=\frac{sum}{count\times(count-1.0)}\times 2.0\) endif if\(s_{i}\leq\tilde{m}\)then if\(countLow+1>threshold\)then \(\tilde{m}=\tilde{m}-\lambda\) \(countHigh=countHigh+1\) else \(countLow=countLow+1\) endif else if\(countHigh+1>count-threshold\)then \(\tilde{m}=\tilde{m}+\lambda\) \(countLow=countLow+1\) else \(countHigh=countHigh+1\) endif endfor return\(\tilde{m}\)
```
**Algorithm 3** EasyQuantile
```
0: Data stream \(S\), quantile \(q\), \(O(1)\) units of memory
0: estimated quantile value \(\tilde{m}\) \(mode=0\)\(\triangleright\) mode of operation: \(MAX\_MIN=1\), \(AVERAGE=2\) \(\tilde{m}=0\) \(max=-\infty\) \(min=+\infty\) \(sum=0\) \(count=0\) \(countLow=0\) \(countHigh=0\) \(\lambda=0\) \(count=0\) \(threshold=0\) \(threshold=0\) \(toggleThreshold=0.7\) if\(q>toggleThreshold\)then \(mode=1\) else \(mode=2\) endif for each\(s_{i}\in S\)do \(count=count+1



## 4 Speed of Convergence

We experimentally determined the speed of convergence to the true quantile of Frugal-1U, Frugal-2U, and EasyQuantile by implementing the sequential versions of the algorithms and keeping track of pairs \((\hat{m}_{i},q_{i})\), \(i=n/100,2n/100,\cdots,99n/100,n\) (i.e., each pair is computed every \(1/100\) of the input stream, whose length is \(n\)). We carried out our experiments using the synthetic datasets shown in Table 1.

In particular, we performed three sets of experiments. First, we assessed the speed of convergence by fixing the quantile to be tracked to \(0.99\) and the dataset size to \(10\) millions, and varying the distribution. Next, we fixed the distribution (to the normal distribution), fixed the quantile to be tracked (to \(0.99\)), and varied the stream size. Finally, we fixed the distribution (to the normal distribution), fixed the dataset size (to \(10\) millions), and varied the quantile to be tracked. Figures 1 and 2 depict the results obtained varying the distribution. As shown in Figure 1a, related to the normal distribution, all of the algorithms require slightly more than \(4\) million items before converging initially to the true quantile at that moment, which then slowly rises. The algorithms track the quantile and reach again the true quantile at about \(9\) million items, then the algorithms closely follow the true quantile evolution until the end of the stream. The behavior depicted for the cauchy distribution in Figure 1b markedly differs between the Frugal-1U and Frugal-2U algorithms on the one side, and EasyQuantile on the other. The former closely follow the true quantile up to about \(9\) million items. The true quantile then rapidly increases and is reached again just at the end of the stream. The EasyQuantile algorithm consistently exhibits problems in tracking the quantile, even though sudden jumps present in the plot show that the algorithm periodically converges \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Dataset** & **Distribution** & **Parameters** & **PDF** \\ \hline D1 & Uniform & [0, 25,000] \\ D2 & \(\chi^{2}\) & \(\alpha=5\) \\ D3 & Exponential & \(\alpha=0.5\) \\ D4 & Log-normal & \(\alpha=1,\beta=1.5\) \\ D5 & Normal & \(\mu=50,\sigma=2\) \\ D6 & Cauchy & \(\alpha=10,000,\beta=1250\) \\ D7 & Extreme Value & \(\alpha=20,\beta=2\) \\ D8 & Gamma & \(a=2,b=4\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Synthetic datasets.