# Parallel and Distributed Frugal Tracking of a Quantile +
## 3 The EasyQuantile Algorithm  
This algorithm has been designed to be implemented in the data plane, taking into account stringent constraints on the hardware resources (limited memory and computing capacity). In particular, it works by updating the quantile estimate \(\hat{m}\) depending on the actual count of the stream items; updates are performed only if required, i.e., if the estimate deviates from the true quantile. A key idea is to distinguish between smaller and larger quantiles using an experimentally determined toggling threshold \(toggleThreshold\), fixed by the authors at 0.7. For small quantiles, the update is smooth, being based on the average of the observed stream items, whilst for large quantiles, the update is more drastic, being based on the current range (max value minus min value). The algorithm begins initializing the variables used internally, then proceeds determining the mode of operation, which can be either \(MAX\_MIN\) if the quantile to be tracked is greater than the toggling threshold or \(AVERAGE\) otherwise. Next, the incoming stream items are processed. The arrival of a new item \(s_{i}\) increases the value of \(count\), which keeps track of the number of observations seen. Only for the first observed item, the quantile estimate \(\hat{m}\) is set to 1 and the algorithm proceeds waiting for the next incoming item. Otherwise, for each successive item, the algorithm computes \(threshold\), a dynamically adjusting threshold given by the product \(count\times quantile\). Next, the algorithm dynamically adjusts the current values of \(max\) and \(min\) and the current value of \(sum\), which is the sum of the values of the observations seen so far. The step of the update is then computed, depending on the mode of operation. The algorithm then selectively updates the quantile estimate depending on the values of \(countLow\) and \(countHigh\). Those variables are initialized to zero and represent, respectively, the number of items whose value is lesser or greater than the current quantile estimate \(\hat{m}\). This allows avoiding sorting to infer the rank of the estimate. If the incoming item \(s_{i}\) is less than or equal to the quantile estimate \(\hat{m}\), the value of \(countLow\) must be increased by one, otherwise the value of \(countHigh\) must be increased by one. Here, the authors take advantage of the fact that, after seeing the \(i\)-th item, the values of \(countLow\) and \(countHigh\) must be respectively equal to \(i\times q\) and \(i\times(1-q)\) if \(\hat{m}\) is equal to the true quantile value. Therefore, if \(countLow+1\) exceeds the dynamically adjusted \(threshold\) value, the current estimate \(\hat{m}\) is greater than the true quantile, and the algorithms updates the estimate by subtracting the previously computed step size \(\lambda\). The reason behind the increase in \(countHigh\) is that, immediately after the update, the estimate is less than its previous value and the authors treat the estimate as if it was an incoming stream item. The other update is symmetric for the case \(s_{i}>\hat{m}\): if \(countHigh+1\) exceeds \(count-threshold\) (i.e., \(i\times(1-q)\)), following the previous argument, the authors update the estimate by adding \(\lambda\) and increasing \(countLow\), again treating the estimate as a stream item. Algorithm 3 provides the pseudo-code for EasyQuantile.