# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm
but then has difficulties until about 8 million items. At that moment, the true quantile begins to drift and the algorithm slowly chases it until convergence at the end of the stream. The uniform distribution, shown in Figure 1c, is characterized by an almost regular and linear behavior exhibited by all of the algorithms with regard to the tracking of the true quantile. Frugal-1U is the slowest, followed by Frugal-2U. Starting from about 1.5 million items, EasyQuantile is consistently faster than the others, even though both Frugal-1U and Frugal-2U converge to the true quantile at the end of the stream. Figure 1d is related to the exponential distribution. The behavior of EasyQuantile, starting at about 1 million items, appears to be close to linear and a final sudden jump allows the algorithm to converge to the true quantile. Both Frugal-1U and Frugal-2U exhibit the same behavior and are able to converge 4 times to the true quantile value before finally converging at the end of the stream. Regarding the \(\chi^{2}\) distribution, depicted in Figure 2a, the behavior of the algorithms is pretty similar to that observed for the exponential distribution, with the EasyQuantile algorithms exhibiting an almost linear trend starting from about 3 million items. Frugal-1U and Frugal-2U, after initially converging at about 6 million items, converge again at about 8.5 million items and then continue to closely track the true quantile value until the end of the stream. Figure 1: Speed of convergence: normal, cauchy, uniform, and exponential distributions. The algorithms' behaviors for the gamma distribution, shown in Figure 2a, are also quite similar to that for the \(\chi^{2}\) and exponential distributions, which is not surprising owing to the relationships between the \(\chi^{2}\), gamma, and exponential distributions. In the case of the log-normal distribution, shown in Figure 2c, all of the algorithms closely track the true quantile until about 5.5 million items. Here, the true quantile value starts drifting. EasyQuantile slowly approaches it with a linear behavior and a sudden jump at the end, whilst Frugal-1U and Frugal-2U are faster in adapting, reach again the true quantile at about 8.5 million items and then closely chase it until the end of the stream. The extreme value distribution is depicted in Figure 2d. As shown, all of the algorithms exhibit a linear trend. However, Frugal-1U and Frugal-2U, starting from about 7.5 million items, modify their behavior and adapt faster than EasyQuantile, better tracking the true quantile until the end of the stream, where, with a sudden jump, EasyQuantile is also able to converge. Next, we analyze the convergence speed when varying the stream size. Results are reported in Figure 3. As shown, we used stream sizes equal to 1, 10, 50, and 100 million items. Note that Figure 3b is a copy of Figure 1a, but is reported here for completeness. Figure 3a is more interesting than the others (which are quite similar with regard to their behavior, already discussed with reference to Figure 1a) since it shows that the Frugal-1U estimate goes down up to 200 thousand items instead of being incremented, and the same behavior is also observed for Frugal-2U (up to about 150 thousand items). Figure 2: Speed of convergence: \(\chi^{2}\), gamma, log-normal, and extreme value distributions. Finally, we analyze the convergence speed with regard to the actual quantile being tracked. In particular, we track equi-spaced quantiles \(0.1,0.2,\cdots,0.8,0.9\), and \(0.99\). We note here that the plot for the \(0.99\) quantile is a copy of Figure 1a but is reported here for completeness. As shown in Figures 4-6, depicting the results obtained by varying the quantile, we observe that for smaller quantiles (\(0.1,0.2\), and \(0.3\)), all of the algorithms overestimate the true quantile value until convergence at the end of the stream. This behavior changes starting from the \(0.4\) quantile on, with an underestimation phase followed by an overestimation one.