## 5 Reducing the Size of \(\mathcal{D}^{Y}_{I,\epsilon}\)  
Our idea for reducing the size is simple; for every \(\mathcal{C}_{J,\lambda,\kappa}\in\mathcal{D}^{Y}_{I,\epsilon}\), its capacity is no longer fixed at \(\kappa=\frac{4}{\epsilon}\log W\); instead, we start with a much smaller capacity, namely \(\frac{4}{\epsilon}\log\log W\), which is allowed to increase gradually during execution. To determine \(\mathcal{C}_{J,\lambda,\kappa}\)'s capacity, we use a variable to keep track of the number \(\bar{f}_{*}(J)\) of items \((a,u)\) with \(u\in J\) that have arrived since \(\mathcal{C}_{J,\lambda,\kappa}\)'s creation. Let \(v_{J}\) be the total value of the nodes in \(\mathcal{C}_{J,\lambda,\kappa}\) when it is created (\(v_{J}\) may not be zero if \(\mathcal{C}_{J,\lambda,\kappa}\) is resulted from the splitting of its parent). The capacity of \(\mathcal{C}_{J,\lambda,\kappa}\) is determined as follows. When \(\frac{(c-1)Y}{\log W}\leq v_{J}+\bar{f}_{*}(J)<\frac{cY}{\log W}\) for some integer \(c\geq 1\), the capacity of \(\mathcal{C}_{J,\lambda,\kappa}\) is \(\kappa(c)=\frac{4c}{\epsilon}\log\log W\), _i.e._, set \(\kappa=\kappa(c)\) and allow \(\kappa(c)\) non-trivial queues in \(\mathcal{C}_{J,\lambda,\kappa}\). Note that when we increase the capacity of \(\mathcal{C}_{J,\lambda,\kappa}\) to \(\kappa(c)\), we do not need to do anything, except that we allow more non-trivial queues (up to \(\kappa(c)\)) in the data structure. Also note that when \(\mathcal{C}_{J,\lambda,\kappa}\) is created during the trimming process, its inherited capacity may be larger than the supposed capacity \(\kappa(c)\); in such case, we simply debit every non-trivial queue until some queue \(Q^{x}_{J,\lambda}\) has \(v(Q^{x}_{J,\lambda})=d(Q^{x}_{J,\lambda})\) and we execute Lines 4 and 5 of the procedure \(\textsc{Process}(\,)\) to make this queue trivial. We repeat the process until the number of non-trivial queues is at most \(\kappa(c)\). The following theorem asserts that \(\mathcal{D}^{Y}_{I,\epsilon}\) maintains the accuracy of its estimates under this new implementation. It gives the revised size and the update time. **Theorem 7**1. _Suppose that_ \(\mathcal{D}^{Y}_{I,\epsilon}\) _is currently covering_ \([p,r_{I}]\)_. For any item_ \(a\in\Sigma\) _and any timestamp_ \(t\in[p,r_{I}]\)_, the estimate_ \(\hat{f}_{a}([t,r_{I}])\) _of_ \(f_{a}([t,r_{I}])\) _obtained by the new_ \(\mathcal{D}^{Y}_{I,\epsilon}\) _satisfies_ \(|\hat{f}_{a}([t,r_{I}])-f_{a}([t,r_{I}])|\leq\epsilon Y\)_._
2. \(\mathcal{D}^{Y}_{I,\epsilon}\) _has size_ \(O(\frac{1}{\epsilon}(\log\log W)\log W)\)_, and supports_ \(O(\log\frac{1}{\epsilon}+\log\log W)\) _update time._  
Proof. : Suppose that \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa(c_{1})},\ldots,\mathcal{C}_{J_{m},\lambda,\kappa(c_{m})}\rangle\). From the fact that we are using \(\mathcal{C}_{J_{i},\lambda,\kappa(c_{i})}\) to monitor \(J_{i}\) we conclude \(\frac{(c_{i}-1)Y}{\log W}\leq v_{J_{i}}+\bar{f}_{*}(J_{i})\). It follows that \(\sum_{1\leq i\leq m}\frac{c_{i}Y}{\log W}\leq\sum_{1\leq i\leq m}(v_{J_{i}}+ \bar{f}_{*}(J_{i}))+\sum_{1\leq i\leq m}\frac{Y}{\log W}\), which is O(Y) because (i) \(|\mathcal{D}^{Y}_{I,\epsilon}|=m=O(\log W)\) and (ii) \(\sum_{1\leq i\leq m}(v_{J_{i}}+\bar{f}_{*}(J_{i}))=O(Y)\) (otherwise \(\mathcal{D}^{Y}_{I,\epsilon}\) would have been trimmed). Thus,  
\[\sum_{1\leq i\leq m}c_{i}=O(\log W) \tag{9}\]  
For Statement (1), the analysis of the accuracy of \(\hat{f}_{a}([t,r_{I}])\) is very similar to that of Theorem 6, except for the following difference: In the proof of Theorem 6, we show that \(d(\textsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq p}^{a})\leq\frac{2(1+ \epsilon)Y}{\kappa}\log W\), and since \(\kappa\) is fixed at \(\frac{4}{\epsilon}\log W\), \(d(\textsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq p}^{a})\leq\epsilon Y\). Here, we also prove that \(d(\textsf{dead}(\mathcal{D}^{Y}_{I,\epsilon})_{\geq p}^{a})\leq\epsilon Y\), but we have to prove it differently because the capacities are no longer fixed.