## 4 Our Data Structure for \(\epsilon\)-Approximate Counting
When \(t=2\epsilon Y/m-1\), the absolute error is \(2\epsilon Y\) which is larger than the required error bound \(\epsilon Y\). To describe the right trimming procedure, we need some basic operations. Consider any \(\mathcal{C}_{J,\lambda,\kappa}\) where \(J=[p,q]\). The following operation splits \(\mathcal{C}_{J,\lambda,\kappa}\) into two smaller data structures \(\mathcal{C}_{J_{\ell},\lambda,\kappa}\) and \(\mathcal{C}_{J_{r},\lambda,\kappa}\) where \(J_{\ell}=[p,m]\) and \(J_{r}=[m+1,q]\) with \(m=\lfloor(p+q)/2\rfloor\). ```
1:for each non-trivial queue \(\mathcal{Q}^{a}_{J,\lambda}\in\mathcal{C}_{J,\lambda,\kappa}\)do
2:if (\(\mathcal{Q}^{a}_{J,\lambda}\) has only one node \(N\) monitoring the whole interval \(J\))then
3: /* refine \(J\) */
4: insert a new node \(N^{\prime}\) immediately to the left of \(N\) with \(v(N^{\prime})=d(N^{\prime})=0\);
5:\(i(N^{\prime})=J_{\ell}\), and \(i(N)=J_{r}\);
6:endif
7: divide \(\mathcal{Q}^{a}_{J,\lambda}\) into two sub-queues \(\mathcal{Q}^{a}_{J_{\ell},\lambda}\) and \(\mathcal{Q}^{a}_{J_{r},\lambda}\) where
8:\(\mathcal{Q}^{a}_{J_{\ell},\lambda}\) contains the nodes monitoring some sub-intervals of \(J_{\ell}\), and
9:\(\mathcal{Q}^{a}_{J_{r},\lambda}\) contains those monitoring some sub-intervals of \(J_{r}\);
10: put \(\mathcal{Q}^{a}_{J_{\ell},\lambda}\) in \(\mathcal{C}_{J_{\ell},\lambda,\kappa}\) and \(\mathcal{Q}^{a}_{J_{r},\lambda}\) in \(\mathcal{C}_{J_{r},\lambda,\kappa}\). 11:endfor
12:/* For a trivial \(\mathcal{Q}^{a}_{J,\lambda}\), its two children in \(\mathcal{C}_{J_{\ell},\lambda,\kappa}\) and \(\mathcal{C}_{J_{r},\lambda,\kappa}\) are also trivial. */
```  
**Algorithm 3**Split(\(\mathcal{C}_{J,\lambda,\kappa}\))  
We say that \(\mathcal{C}_{J_{\ell},\lambda,\kappa}\) and \(\mathcal{C}_{J_{r},\lambda,\kappa}\) are the left and right child of \(\mathcal{C}_{J,\lambda,\kappa}\), respectively. Figure 3 gives an example of Split(\(\mathcal{C}_{[1,8],\lambda,\kappa}\)), the split of \(\mathcal{C}_{[1,8],\lambda,\kappa}\), which has three non-trivial queues \(Q^{a}_{I,\lambda},Q^{b}_{I,\lambda}\) and \(Q_{I,\lambda}^{c}\), into \(\mathcal{C}_{[1,4],\lambda,\kappa}\) and \(\mathcal{C}_{[5,8],\lambda,\kappa}\). Note that the queues for \(b\) and \(c\) in \(\mathcal{C}_{[1,4],\lambda,\kappa}\) are trivial and we have not stored them. Using Split\(()\), we can trim, for example, \(\mathcal{C}_{[p,p+1],\lambda,\kappa}\) into \(\mathcal{C}_{[p+1,p+1],\lambda,\kappa}\) as follows: Split \(\mathcal{C}_{[p,p,p+1],\lambda,\kappa}\) into \(\mathcal{C}_{[p,p],\lambda,\kappa}\) and \(\mathcal{C}_{[p+1,p+1],\lambda,\kappa}\), and throw away \(\mathcal{C}_{[p,p],\lambda,\kappa}\). The following recursive procedure LeftRefine\(()\) generalizes this idea for larger \(J\): Given \(\mathcal{C}_{J,\lambda,\kappa}=\mathcal{C}_{[p,q],\lambda,\kappa}\), it returns a list \(\langle\mathcal{C}_{J_{0},\lambda,\kappa},\mathcal{C}_{J_{1},\lambda,\kappa}, \ldots,\mathcal{C}_{J_{m},\lambda,\kappa}\rangle\) where the \(J_{i}\)'s form a partition of \([p,q]\), and \(J_{0}=[p,p]\). Throwing away \(\mathcal{C}_{J_{0},\lambda,\kappa}\), and the remaining \(\mathcal{C}_{J_{i},\lambda,\kappa}\)'s all together monitor \([p+1,q]\). ```
1:if\((|[p,q]|=|[p,p]|=1)\)then
2: return \(\langle\mathcal{C}_{[p,p],\lambda,\kappa}\rangle\);
3:else
4: split \(\mathcal{C}_{[p,q],\lambda,\kappa}\) into its left child \(\mathcal{C}_{[p,m],\lambda,\kappa}\) and right child \(\mathcal{C}_{[m+1,q],\lambda,\kappa}\)
5: /* where \(m=\lfloor(p+q)/2\rfloor\)*/;
6:\(L=\text{LeftRefine}(\mathcal{C}_{[p,m],\lambda,\kappa})\);
7: suppose \(L=\langle\mathcal{C}_{J_{0},\lambda,\kappa},\mathcal{C}_{J_{1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{k},\lambda,\kappa}\rangle\);
8: return \(\langle\mathcal{C}_{J_{0},\lambda,\kappa},\ldots,\mathcal{C}_{J_{k},\lambda, \kappa},\mathcal{C}_{[m+1,q],\lambda,\kappa}\rangle\);
9:endif
```  
**Algorithm 3**Split of \(\mathcal{C}_{[1,8],\lambda,\kappa}\).