## 4 Our Data Structure for \(\epsilon\)-Approximate Counting
**Theorem 4**:
* _The data structure_ \(\mathcal{D}_{I,\epsilon}\) _has size_ \(O\big{(}\frac{1}{\epsilon}(\log\log W)(\log W)\log(\frac{\epsilon B}{\log W}) \big{)}\) _words, and supports_ \(O\big{(}(\log\frac{1}{\epsilon}+\log\log W)\log(\frac{\epsilon B}{\log W}) \big{)}\) _update time._
* _Given_ \(\mathcal{D}_{I,\epsilon}\)_, we can find, for any_ \(a\in\Sigma\) _and_ \(t\in I\)_, an estimate of_ \(\hat{f}_{a}([t,r_{I}])\) _of_ \(f_{a}([t,r_{I}])\) _such that_ \(|\hat{f}_{a}([t,r_{I}])-f_{a}([t,r_{I}])|\leq\epsilon f_{*}([t,r_{I}])\)_._  
Statement (i) is straightforward because there are \(\log B-\log(\frac{1}{\epsilon}\log W)\) different \(\mathcal{D}_{I,\epsilon}^{Y}\), each has size \(O(\frac{1}{\epsilon}(\log\log W)\log W)\) and takes \(O(\log\frac{1}{\epsilon}+\log\log W)\) time for an update. For Statement (ii), we describe how to get the estimate and analyze its accuracy. First, we use \(\mathcal{B}_{I,\epsilon}\) to get the estimate \(\hat{f}_{*}([t,r_{I}])\). If \(\hat{f}_{*}([t,r_{I}])\leq\frac{1}{\epsilon}\log W\), then \(f_{*}([t,r_{I}])\leq\hat{f}_{*}([t,r_{I}])\leq\frac{1}{\epsilon}\log W\) and we can use the brute-force data structure to find \(f_{a}([t,r_{I}])\) exactly. Otherwise, we determine the \(i\) with \(2^{i-1}<\hat{f}_{*}([t,r_{I}])\leq 2^{i}\). Note that  
* \(i\geq\log(\frac{1}{\epsilon}\log W)+1\) and we have the data structure \(\mathcal{D}_{I,\frac{1}{\epsilon}}^{2^{i}}\), and* \(f_{*}([t,r_{I}])\leq\hat{f}_{*}([t,r_{I}])\leq 2^{i}\). We use \(\mathcal{D}^{2^{i}}_{I,\frac{4}{4}}\) to obtain an estimate \(\hat{f}_{a}([t,r_{I}])\) with \(|\hat{f}_{a}([t,r_{I}])-f_{a}([t,r_{I}])|\leq(\frac{\epsilon}{4})2^{i}\). By Equation (7), \(2^{i-1}<\hat{f}_{*}([t,r_{I}])\leq(1+\epsilon)f_{*}([t,r_{I}])\). Combining the two inequalities we have  
\[|\hat{f}_{a}([t,r_{I}])-f_{a}([t,r_{I}])|\leq 2(\frac{\epsilon}{4})(2^{i-1})<2( \frac{\epsilon}{4})(1+\epsilon)f_{*}([t,r_{I}])\leq\epsilon f_{*}([t,r_{I}])\]  
We now describe the construction of \(\mathcal{D}^{Y}_{I,\epsilon}\). First, we describe an \(O(\frac{1}{\epsilon}(\log W)^{2})\)-space version of the data structure. Then, we show in the next section how to reduce the space to \(O(\frac{1}{\epsilon}\log\log W\log W)\). In our discussion, we fix \(\lambda=\epsilon Y/\log W\) and \(\kappa=\frac{4}{\epsilon}\log W\). Initially, \(\mathcal{D}^{Y}_{I,\epsilon}\) is just the data structure \(\mathcal{C}_{I,\lambda,\kappa}\). By Lemma 3, we know that its size is \(O(\frac{f_{*}(I)}{\lambda}+\kappa)=O(\frac{f_{*}(I)}{\epsilon Y}\log W+\frac{ 1}{\epsilon}\log W)\), which is \(O(\frac{1}{\epsilon}\log W)\) when \(f_{*}(I)\leq Y\). However, it is much larger than \(\frac{1}{\epsilon}\log W\) when \(f_{*}(I)\gg Y\), and to maintain small space usage in such case, we trim \(\mathcal{C}_{I,\lambda,\kappa}\) by throwing away a significant number of nodes. This is acceptable because \(\mathcal{C}_{I,\lambda,\kappa}\) only guarantees good estimates for those \(t\in I\) with \(f_{*}([t,r_{I}])\leq Y\). The trimming process is rather tricky. The natural idea of throwing away all the nodes to the left of \(t\) when we find \(f_{*}([t,r_{I}])>Y\) does not work because the resulting data structure may return estimates with error larger than the required \(\epsilon Y\) bound. For example, let \(I=[1,W]\). For each item \(a_{i}\in\{a_{1},a_{2},\ldots,a_{\kappa-1}\}\), there are \(m=Y/\kappa\) copies of \((a_{i},t+1)\) arrive at time \(W+t\) for every \(t\in[0,W-1]\). Also, there are \(m\) copies of \((a,W)\) arrive at time \(W+t\) for every \(t\in[0,W-1]\). Hence, at each time \(W+t\), there are \(m\kappa=Y\) items with timestamps in \([t,W]\) arrives, \(m\) items for each of the \(\kappa\) item name in \(\{a,a_{1},\ldots,a_{\kappa-1}\}\). We are interested in the accuracy of the estimate \(\hat{f}_{a}([W,W])\). It can be verified that at each time \(W+t\), Lines 4-5 of the procedure Process\((\,)\) will eventually trivialize \(Q^{a}_{I,\lambda}\) and thus \(\hat{f}_{a}([W,W])=0\). Since \(f_{a}([W,W])=(t+1)m\), \(|\hat{f}_{a}([W,W])-f_{a}([W,W])|=(t+1)m\).