# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
Overall, the algorithms are better at tracking higher rather than smaller quantiles. Figure 3: Speed of convergence varying the stream size. Figure 4: Speed of convergence varying the quantile: smaller quantiles. Figure 5: _Cont._

## 5 Parallelizing the Frugal Algorithm

In this section, we design parallel, message-passing based versions of algorithms. Since the parallel design is the same for all of the algorithms, we shall illustrate these with reference only to Frugal-1U. A corresponding distributed version (this also applies to all of the algorithms) can be easily derived from the parallel one and shall be discussed along with the parallel one. In order to parallelize Frugal-1U, we begin by partitioning the input among the available processors. For the parallel version, we assume that the input consists of a dataset \(S\) of size \(n\). Therefore, assuming that \(p\) processors are available, the input is partitioned so that each processor is responsible for either \(\lfloor n/p\rfloor\) or \(\lceil n/p\rceil\) items. For the distributed version, each processor will instead process a sub-stream \(S_{i}\) of length \(n_{i}\), \(i=1,\cdots,p\). Each processor will update locally its own estimate of the quantile \(q\) being sought. After processing its input, the processors in the parallel version will engage in a parallel reduction operation, required to aggregate the local estimates obtained. Similarly, in the distributed version, the processors will send their local information to a designated processor, which will take care of performing the required aggregation step to obtain the global estimate associated to the union of the sub-streams \(\cup_{i=1}^{p}S_{i}\). Figure 5: Speed of convergence varying the quantile: larger quantiles. Figure 6: Speed of convergence varying the quantile: largest quantiles. The information required for the final aggregation operation is the same for both the parallel and the distributed version, namely for each processor \(i=1,\cdots,p\), we need a pair \((\tilde{m}_{i},n_{i})\), where \(\tilde{m}_{i}\) and \(n_{i}\) are, respectively, the local estimate and the number of items processed by the \(i\)-th processor. The local results obtained by the processors are aggregated in parallel by performing a reduction operation in which the weighted average of the local estimates is computed using the \(n_{i}\) as weights. Note that \(\sum_{i=1}^{p}n_{i}=n\). Letting \(\tilde{m}_{g}\) denote the global estimate for the input dataset \(S\) (parallel case) or the union \(\cup_{i=1}^{p}S_{i}\) (distributed case), it holds that

\[\tilde{m}_{g}=\frac{\sum_{i=1}^{p}\tilde{m}_{i}n_{i}}{n}. \tag{3}\]

Algorithms 4 and 5 provide, respectively, the pseudo-code for the parallel version of Frugal-1U and the user's defined parallel reduction operator in charge of computing the global estimate. In Algorithm 4, we assume that the input is a dataset \(D\) of size \(n\) stored into an array \(A\). The input parameters are, respectively, \(A\), \(n\), \(p\), and \(q\), where \(A\) is the input array, \(n\) the length of \(A\), \(p\) the number of processors we use in parallel and \(q\) the quantile to be estimated. ```
0:\(A\), an array; \(n\), the length of \(A\); \(p\), the number of processors; \(q\), the quantile to be estimated
0:estimated quantile value \(\tilde{m}\) // let \(id\) be the rank of the processor \((0\leq id\leq p-1)\) \(left=\lfloor id\ n/p\rfloor\) \(right=\lfloor(id+1)\ n/p\rfloor-1\) \(\tilde{m}_{id}=\textsc{Frugal-1U}(A,left,right,q)\) \(size_{id}=right-left+1\) \((\tilde{m}_{g},w_{g})=\textsc{ParallelReduction}(\tilde{m}_{id},size_{id})\) if\(id==0\)then return\(\tilde{m}_{g}\) endif
```

**Algorithm 4** Parallel Frugal-1U

The algorithm begins by partitioning the input array; \(left\) and \(right\) are, respectively, the indices of the first and last element of the array assigned to the process with rank \(id\) by the domain decomposition performed. This is done by using a simple block distribution.