## 4 Our Data Structure for \(\epsilon\)-Approximate Counting  
The first shortcoming of the approach given in Section 3 is easy to overcome: a natural idea is to maintain \(\mathcal{C}_{I,\lambda_{i},\frac{1}{\epsilon}}\) for different \(\lambda_{i}\) to handle different possible values of \(f_{*}(I)\). The second shortcoming is more fundamental. To overcome it, we need to modify \(\mathcal{C}_{I,\lambda,\kappa}\) substantially. The result is a new and complicated data structure \(\mathcal{D}_{I,\epsilon}^{Y}\), where \(Y\) is an integer determining the accuracy. As asserted in Theorem 7 below, this data structure uses \(O(\frac{1}{\epsilon}\log W\log\log W)\) space, supports \(O(\log\frac{1}{\epsilon}+\log\log W)\) update time, and for any \(t\in I\), it offers the following special guarantee:  
* When \(f_{*}([t,r_{I}])\leq Y\), \(\mathcal{D}_{I,\epsilon}^{Y}\) can return, for any item \(a\), an estimate \(\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 Y\). * When \(f_{*}([t,r_{I}])>Y\), \(\mathcal{D}_{I,\epsilon}^{Y}\) does not have any error bound on its estimate \(\hat{f}_{a}([t,r_{I}])\). Before giving the details of \(\mathcal{D}_{I,\epsilon}^{Y}\), let us explain how to use it to build the data structure \(\mathcal{D}_{I,\epsilon}\) mentioned in Section 2 for the \(\epsilon\)-approximate counting problem. To build \(\mathcal{D}_{I,\epsilon}\), we need another \(O(\frac{1}{\epsilon}\log W\log\frac{\epsilon B}{\log W})\)-space data structure \(\mathcal{B}_{I,\epsilon}\), which is a simple adaption of the data structure \(\mathcal{B}_{\epsilon}\) of [PERSON] _et al_. [1] for the \(\epsilon\)-approximate basic counting problem; \(\mathcal{B}_{I,\epsilon}\) enables us to find, for any \(t\in I\), an estimate \(\hat{f}_{*}([t,r_{I}])\) of \(f_{*}([t,r_{I}])\) such that  
\[f_{*}([t,r_{I}])\leq\hat{f}_{*}([t,r_{I}])\leq(1+\epsilon)f_{*}([t,r_{I}]) \tag{7}\]  
\(\mathcal{B}_{I,\epsilon}\) is implemented as follows. During execution, we maintain the data structure \(\mathcal{B}_{\epsilon/4}\) of [PERSON] _et al_. to count the items in the sliding window. When \(\tau_{\text{cur}}=r_{I}\), we duplicate \(\mathcal{B}_{\epsilon/4}\) and get \(\mathcal{B}^{\prime}\). Then, \(\mathcal{B}^{\prime}\) is updated as if \(\tau_{\text{cur}}\) was fixed at \(r_{I}\). To get the estimate \(\hat{f}_{*}([t,r_{I}])\), we first obtain an estimate \(f^{\prime}\) of \(f_{*}([t,r_{I}])\) from \(\mathcal{B}^{\prime}\), which satisfies \(|f^{\prime}-f_{*}([t,r_{I}])|\leq\frac{\epsilon}{4}f_{*}([t,r_{I}])\). Then, \(\hat{f}_{*}([t,r_{I}])=\frac{1}{1-\epsilon/4}f^{\prime}\). It can be verified that \(\hat{f}_{*}([t,r_{I}])\) satisfies Equation (7). Our data structure \(\mathcal{D}_{I,\epsilon}\) is composed of (i) \(\mathcal{B}_{I,\epsilon}\), and (ii) \(\mathcal{D}_{I,\epsilon/4}^{2^{i}}\) for each integer \(i\) from \(\log(\frac{1}{\epsilon}\log W)+1\) to \(\log B\). It also maintains a brute-force \(O(\frac{1}{\epsilon}\log W)\)-space data structure for remembering the \(\frac{1}{\epsilon}\log W\) items \((a,u)\) with the largest \(u\in I\); this brute-force data structure will be used for finding \(\hat{f}_{a}([t,r_{I}])\) only when \(f_{*}([t,r_{I}])\leq\frac{1}{\epsilon}\log W\).