## 4 Our Data Structure for \(\epsilon\)-Approximate Counting
For example, LeftRefine(\(\mathcal{C}_{[1,8],\lambda,\kappa}\)) gives us the list \(\langle\mathcal{C}_{[1,1],\lambda,\kappa},\mathcal{C}_{[2,2],\lambda,\kappa},\mathcal{C}_{[3,4],\lambda,\kappa},\mathcal{C}_{[5,8],\lambda,\kappa}\rangle\). Note that \(J_{0}=[p,p]\) because the recursion stops only when \(|[p,q]|=1\). The list returned by LeftRefine(\(\mathcal{C}_{[p,q],\lambda,\kappa}\)) has another useful property, which we describe below. Given \(L=\langle\mathcal{C}_{Z_{1},\lambda,\kappa},\ldots,\mathcal{C}_{Z_{k},\lambda, \kappa}\rangle\), we say that \(L\) is an _interesting-partition_ covering the interval \(J\) if (i) the \(Z_{i}\)'s are all interesting intervals and form a partition of \(J\); and (ii) for \(1\leq i<k\), \(Z_{i}\) is to the left of \(Z_{i+1}\), and \(|Z_{i}|\leq\frac{1}{2}|Z_{i+1}|\). The fact below can be verified by induction on the length of the list returned by \(\text{LeftRefine}(\,)\). **Fact 3**: _Let \(J\) be an interesting interval, and \(L=\langle\mathcal{C}_{J_{0},\lambda,\kappa},\ldots,\mathcal{C}_{J_{m}, \lambda,\kappa}\rangle\) be the list returned by \(\text{LeftRefine}(\mathcal{C}_{J,\lambda,\kappa})\). Then, the list \(\langle\mathcal{C}_{J_{1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{m},\lambda, \kappa}\rangle\) (i.e., the list obtained by throwing away the head \(\mathcal{C}_{J_{0},\lambda,\kappa}\) of \(L\)) is an interesting-partition covering \([p+1,q]\)._  
For example, if \([1,8]\) is an interesting interval, then the list \(\langle\mathcal{C}_{[2,2],\lambda,\kappa}\mathcal{C}_{[3,4],\lambda,\kappa}, \mathcal{C}_{[5,8],\lambda,\kappa}\rangle\) obtained by throwing away the first element \(\mathcal{C}_{[1,1],\lambda,\kappa}\) from \(\text{LeftRefine}(\mathcal{C}_{[1,8],\lambda,\kappa})\) is an interesting-partition covering \([2,8]\). We now give details of \(\mathcal{D}^{Y}_{I,\epsilon}\). Initially, it is the interesting-partition \(\langle\mathcal{C}_{I,\lambda,\kappa}\rangle\) covering the whole interval \(I=[\ell_{I},r_{I}]\). Throughout the execution, we maintain the following invariant:  
\((**)\): \(\mathcal{D}^{Y}_{I,\epsilon}\) is an interesting-partition covering some \([p,r_{I}]\subseteq I\). When \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{J_{1},\lambda,\kappa},\ldots, \mathcal{C}_{J_{m},\lambda,\kappa}\rangle\) is covering \([p,r_{I}]\), it only guarantees good estimates of \(f_{a}([t,r_{I}])\) for \(t\in[p,r_{I}]\), and this estimate is obtained by  
\[\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(\mathcal{C}_{J_{h},\lambda,\kappa})_{ \geq t}^{a})+\sum_{h+1\leq i\leq m}v(\mathsf{alive}(\mathcal{C}_{J_{h},\lambda,\kappa})^{a})\]  
(or equivalently, \(\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(Q^{a}_{J_{h},\lambda})_{\geq t})+\sum_ {h+1\leq i\leq m}v(\mathsf{alive}(Q^{a}_{J_{h},\lambda}))\), where \(J_{h}\) is the interval in \(\{J_{1},J_{2},\ldots,J_{m}\}\) that covers \(t\). When an item \((a,u)\) with \(u\in[p,r_{I}]\) arrives, we find the unique \(\mathcal{C}_{J_{l},\lambda,\kappa}\) in \(\mathcal{D}^{Y}_{I,\epsilon}\) where \(u\in J_{i}\), update it by calling \(\mathcal{C}_{J_{i},\lambda,\kappa}\).Process\(((a,u))\). Note that this update has no effect on the other \(\mathcal{C}_{J,\lambda,\kappa}\) in \(\mathcal{D}^{Y}_{I,\epsilon}\). During execution, we also keep track of the largest timestamp \(p_{\tt max}\in I\) such that the estimate \(\hat{f}_{*}([p_{\tt max},r_{I}])\) given by \(\mathcal{B}_{I,\epsilon}\) is greater than \((1+\epsilon)Y\) (which implies \(f_{*}([p_{\tt max},r_{I}])>Y\) because of Equation (7)). As soon as \(p_{\tt max}\) falls in the interval covered by \(\mathcal{D}^{Y}_{I,\epsilon}\), we use the following procedure to trim \(\mathcal{D}^{Y}_{I,\epsilon}\) to cover the smaller interval \([p_{\tt max}+1,r_{I}]\). Suppose that \(L=\langle\mathcal{C}_{J_{1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{m},\lambda,\kappa}\rangle\) is an interesting-partition covering \([p,r_{I}]\), and \(t\in[p,r_{I}]\). Trim\((L,\,t)\) constructs an interesting-partition covering \([t+1,r_{I}]\) recursively as follows.