## 3 A Simple Data Structure For Frequency Estimation
Furthermore, note that for \(1\leq i<k\), \(J_{k}\subset J_{i}\) because (i) \(t\) is in both \(J_{i}\) and \(J_{k}\); (ii) \(J_{k}\) is the smallest interval; and (iii) interesting intervals do not cross; thus \(J_{k}\) is a descendant of \(J_{i}\), and together with Fact 1, \(k\leq\log W\). By Line 3 of the procedure \(\text{Update}(\,)\), \(v_{\mathsf{add}}(N_{i},J_{i})\leq\lambda\) for \(1\leq i\leq k\). It follows that \(S_{o}\leq\lambda\log W\). For the first inequality of the lemma, it is clearer to use \(\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{ \geq t})\). Note that every arrived item \((a,u)\) with \(u\in[t,r_{I}]\) increments the value of some node in \(\mathsf{node}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t}\); thus \(f_{a}([t,r_{I}])\leq v(\mathsf{node}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{ \geq t})\) and  
\[f_{a}([t,r_{I}])-v(\mathsf{alive}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t} )\leq v(\mathsf{node}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})-v(\mathsf{ alive}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})=v(\mathsf{dead}( \mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})\]  
From Lines 4-6 of the procedure \(\text{Process}(\,)\), when we delete a node \(N\), \(v(N)=d(N)\). Hence, \(v(\mathsf{dead}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})=d(\mathsf{dead }(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})\), which is equal to the total number of debt operations made to these dead nodes. Since whenever we make a debit operation to \(Q^{a}_{I,\lambda}\), we will make a debit operation to \(\kappa-1\) other queues,  
\[\kappa\cdot d(\mathsf{dead}(\mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})\leq d (\mathsf{node}(\mathcal{C}_{I,\lambda,\kappa}))\leq v(\mathsf{node}(\mathcal{ C}_{I,\lambda,\kappa}))=f_{*}(I) \tag{6}\]  
In summary, we have \(f_{a}([t,r_{I}])-\hat{f}_{a}([t,r_{I}])=f_{a}([t,r_{I}])-v(\mathsf{alive}( \mathcal{C}_{I,\lambda,\kappa})^{a}_{\geq t})\leq v(\mathsf{dead}(\mathcal{ C}_{I,\lambda,\kappa})^{a}_{\geq t})=d(\mathsf{dead}(\mathcal{C}_{I, \lambda,\kappa})^{a}_{\geq t})\leq f_{*}(I)/\kappa,\) and the first inequality of the lemma follows. For the space, we say that a node is born-rich if it is created because of Line 5 of the procedure \(\text{Update}(\,)\) (and thus has \(\lambda\) items under its belt); otherwise it is born-poor. Obviously, there are at most \(f_{*}(I)/\lambda\) born-rich nodes. For born-poor nodes, we need to store at most \(\kappa\) of them because every queue has one born-poor node (the rightmost one), and we only need to store at most \(\kappa\) non-trivial queues; the space bound follows. If we set \(\lambda=\lambda_{i}=\epsilon 2^{i}/\log W\) and \(\kappa=\frac{1}{\epsilon}\), then Lemma 3 asserts that \(\mathcal{C}_{I,\lambda,\kappa}=\mathcal{C}_{I,\lambda_{i},\frac{1}{\epsilon}}\) is an \(O(\frac{f_{*}(I)}{\epsilon 2^{i}}\log W+\frac{1}{\epsilon})\)-space data structure that enables us to obtain, for any item \(a\in U\) and any timestamp \(t\in I\), an estimate \(\hat{f}_{a}([t,r_{I}])\) that satisfies  
Figure 1:0  
If \(f_{*}(I)\) does not vary too much, we can determine the \(i\) such that \(f_{*}(I)\approx 2^{i}\), and \(\mathcal{C}_{I,\lambda_{i},\frac{1}{\epsilon}}\) is an \(O(\frac{1}{\epsilon}\log W)\) space data structure that guarantees an error bound of \(O(\epsilon f_{*}(I))\). However, this approach has two obvious shortcomings:  
1. \(f_{*}(I)\) may vary from some small value to a value as large as \(B\), the maximum number of items falling in a window of size \(W\); hence, there may not be any fixed \(i\) that always satisfies \(f_{*}(I)\approx 2^{i}\). 2. To estimate \(f_{a}([t,r_{I}])\), we need an error bound of \(\epsilon f_{*}([t,r_{I}])\), not \(\epsilon f_{*}(I)\). We will explain how to overcome these two shortcomings in the next section.