## 4 Our Data Structure for \(\epsilon\)-Approximate Counting
```
1:find the unique \(\mathcal{C}_{J_{i},\lambda,\kappa}\) in \(L\) such that \(t\in J_{i}\);
2:\(L^{\prime}=\)LeftRefine(\(\mathcal{C}_{J_{i},\lambda,\kappa}\));
3: suppose \(L^{\prime}=\langle\mathcal{C}_{K_{0},\lambda,\kappa},\mathcal{C}_{K_{1}, \lambda,\kappa},\ldots,\mathcal{C}_{K_{\ell},\lambda,\kappa}\rangle\);
4:if (\(K_{0}=[t,t]\)) then
5: return \(\langle\mathcal{C}_{K_{1},\lambda,\kappa},\ldots,\mathcal{C}_{K_{\ell}, \lambda,\kappa},\mathcal{C}_{J_{t+1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{m},\lambda,\kappa}\rangle\);
6: /* _i.e._, throw away \(\mathcal{C}_{J_{1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{l-1},\lambda,\kappa}\) and \(\mathcal{C}_{K_{0},\lambda,\kappa}\) */
7: /* and return an interesting-partition covering \([t+1,r_{I}]\). */
8:else
9: return Trim\((\langle\mathcal{C}_{K_{1},\lambda,\kappa},\ldots,\mathcal{C}_{K_{\ell},\lambda, \kappa},\mathcal{C}_{J_{t+1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{m},\lambda,\kappa}\rangle,t)\). 10: /* throw away \(\mathcal{C}_{J_{1},\lambda,\kappa},\ldots,\mathcal{C}_{J_{l-1},\lambda,\kappa}\) and \(\mathcal{C}_{K_{0},\lambda,\kappa}\). */
11:endif
12:endif
13:end if
```  
**Algorithm 1**\(\mathcal{D}^{Y}_{I,\epsilon}\). Trim\((L,\,t)\)For example, Figure 4 shows that when \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{[2,2],\lambda,\kappa},\mathcal{C}_ {[3,4],\lambda,\kappa},\mathcal{C}_{[5,8],\lambda,\kappa}\rangle\), Trim(\(\mathcal{D}^{Y}_{I,\epsilon},3\)) return \(\langle\mathcal{C}_{[4,4],\lambda,\kappa},\mathcal{C}_{[5,8],\lambda,\kappa}\rangle\). Based on Fact 3, it can be verified inductively that after \(\mathcal{D}^{Y}_{I,\epsilon}\leftarrow\text{\rm Trim}(\mathcal{D}^{Y}_{I, \epsilon},p_{\mathtt{max}})\), the new \(\mathcal{D}^{Y}_{I,\epsilon}\) is an interesting-partition covering \([p_{\mathtt{max}}+1,r_{I}]\); Invariant (\(**\)) is preserved. In the rest of this section, we analyze the size of \(\mathcal{D}^{Y}_{I,\epsilon}\) and the accuracy of its estimates. **Figure 4.** Trim(\(\langle\mathcal{C}_{[2,2],\lambda,\kappa},\mathcal{C}_{[3,4],\lambda,\kappa}, \mathcal{C}_{[5,8],\lambda,\kappa}\rangle,3\)). Let All be the set of all \(\mathcal{C}_{J,\lambda,\kappa}\)'s that ever exist, _i.e._, if \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}\), then either (i) it is currently in \(\mathcal{D}^{Y}_{I,\epsilon}\); or (ii) it has been in \(\mathcal{D}^{Y}_{I,\epsilon}\) some time earlier in the execution, but is thrown away during some trimming of \(\mathcal{D}^{Y}_{I,\epsilon}\). For any \(p\in I\), define  
\[\textsc{All}_{\geq p}=\big{\{}\mathcal{C}_{J,\lambda,\kappa}\mid\mathcal{C}_{ J,\lambda,\kappa}\in\textsc{All},\text{ and }J\text{ covers or is to the right of }p\big{\}}\]  
Let \(v_{\mathtt{add}}(\mathcal{C}_{J,\lambda,\kappa})\) be the total value added to the nodes of \(\mathcal{C}_{J,\lambda,\kappa}\) during its lifespan. We now derive an upper bound on \(\sum_{\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}_{\geq p}}v_{\mathtt{add}} (\mathcal{C}_{J,\lambda,\kappa})\), which is crucial for getting a tight error bound on the accuracy of \(\mathcal{D}^{Y}_{I,\epsilon}\)'s estimates. Recall that initially \(\mathcal{D}^{Y}_{I,\epsilon}=\langle\mathcal{C}_{I,\lambda,\kappa}\rangle\) and thus \(\mathcal{C}_{I,\lambda,\kappa}\in\textsc{All}\). For any other \(\mathcal{C}_{J,\lambda,\kappa}\in\textsc{All}\), \(\mathcal{C}_{J,\lambda,\kappa}\) must be a child of some \(\mathcal{C}_{H,\lambda,\kappa}\in\textsc{All}\) (_i.e._, \(\mathcal{C}_{J,\lambda,\kappa}\) is obtained from \(\text{\rm Split}(\mathcal{C}_{H,\lambda,\kappa})\)). Given \(\mathcal{C}_{J,\lambda,\kappa}\) and \(\mathcal{C}_{H,\lambda,\kappa}\), we say that \(\mathcal{C}_{J,\lambda,\kappa}\) is a descendant of \(\mathcal{C}_{H,\lambda,\kappa}\), and \(\mathcal{C}_{H,\lambda,\kappa}\) is an ancestor of \(\mathcal{C}_{J,\lambda,\kappa}\), if either (i) \(\mathcal{C}_{J,\lambda,\kappa}\) is a child of \(\mathcal{C}_{H,\lambda,\kappa}\), or (ii) it is a child of some of \(\mathcal{C}_{H,\lambda,\kappa}\)'s descendants.