# Parallel and Distributed Frugal Tracking of a Quantile +
## 2 The Frugal Algorithm  
Among the many algorithms that have been designed for tracking quantiles in a streaming setting, Frugal, besides being fast and accurate, also restricts by design the amount of memory that can be used. It is well known that in the streaming setting, the main goal is to deliver a high-quality approximation of the result (this may provide either an additive or a multiplicative guarantee) by using the lowest possible amount of space. In practice, there is a tradeoff between the amount of space used by an algorithm and the corresponding accuracy that can be achieved. Surprisingly, Frugal-1U only requires one unit of memory to track a quantile. The authors have also designed a variant for the algorithm that uses two units of memory, Frugal-2U. Algorithm 1 provides the pseudo-code for Frugal-1U. ```
Data stream \(S\), quantile \(q\), one unit of memory \(\bar{m}\)
``` estimated quantile value \(\bar{m}\) \(\bar{m}=0\) for each\(s_{i}\in S\)do \(rand=random(0,1)\) if\(s_{i}>\bar{m}\) and \(rand>1-q\)then \(\bar{m}=\bar{m}+1\) elseif\(s_{i}<\bar{m}\) and \(rand>q\)then \(\bar{m}=\bar{m}-1\) endif endfor return\(\bar{m}\) ```
**Algorithm 1** Frugal-1U  
The algorithm works as follows. First, \(\bar{m}\) is initialized to zero, but the authors also suggest to set it to the value of the first incoming stream item in order to accelerate the convergence. This variable will be dynamically updated each time a new item \(s_{i}\) arrives from the input stream \(S\), and its value represents the estimate of the quantile \(q\) being tracked. The update is quite simple, since it only requires being increased or decreased by one. Specifically, a random number \(0<rand<1\) is generated by using a pseudo-random number generator (the call \(random(0,1)\) in the pseudo-code) and if the incoming stream item is greater than the estimate \(\bar{m}\) and \(rand>1-q\), then the estimate \(\bar{m}\) is increased, otherwise it is decreased. Obviously, the algorithm is really fast and can process an incoming item in worst-case \(O(1)\) time. Therefore, a stream of length \(n\) can be processed in worst-case \(O(n)\) time and \(O(1)\) space. Despite its simplicity, the algorithm provides good accuracy, as shown by the authors in [21]. However, the proof is challenging since the algorithm's analysis is quite involved. The complexity in the worst case is \(O(n)\), since \(n\) items are processed in worst case \(O(1)\) time. Finally, the algorithm has been designed to deal with an input stream consisting of integer values distributed over the domain \([\mathcal{U}]=\{1,2,3,\ldots,\mathcal{U}\}\). This is not a limitation though, owing to the fact that one can process a stream of real values as follows: fix a desired precision, say \(10^{3}\), then each incoming stream item with real value can be converted to an integer by multiplying it by \(10^{3}\) and then truncating the result by taking the floor. If the maximum number of digits following the decimal point is known in advance, truncation may be avoided altogether: letting \(m\) be the maximum number of digits following the decimal point, it suffices to multiply by \(10^{m}\). Obviously, the estimated quantile may be converted back to a real number by dividing the result by the fixed precision selected or by \(10^{m}\). Next, we present the Frugal-2U, shown as pseudo-code in Algorithm 2. This technique is similar to Frugal-1U, but it aims to produce a better quantile estimate utilising just two units of memory for the variables \(\bar{m}\) (the estimate) and \(step\), which denotes the update size. It is worth noting that the variable \(sign\) can be represented with only one bit and is used to decide whether the estimate should be incremented or decremented. The \(step\) size is dynamically increased or decreased on the basis of the values of the incoming stream items. The update process depends on the function \(f(x)\), and works as follows: if the incoming item falls on the same side of the current estimate, then the variable _step_ is increased; otherwise, it is decreased.