## 3 A Simple Data Structure For Frequency Estimation
For any queue \(Q^{a}_{I,\lambda}\), let \(\mathsf{alive}(Q^{a}_{I,\lambda})\) be the set of nodes currently in \(Q^{a}_{I,\lambda}\), \(\mathsf{dead}(Q^{a}_{I,\lambda})\) be those nodes of \(Q^{a}_{I,\lambda}\) that have already been deleted (because of Line 5 of the procedure \(\mathrm{Process}(\,)\)), and \(\mathsf{node}(Q^{a}_{I,\lambda})=\mathsf{alive}(Q^{a}_{I,\lambda})\cup\mathsf{ dead}(Q^{a}_{I,\lambda})\). Note that the estimate \(\hat{f}_{a}([t,r_{I}])\) is the value sum of the nodes in \(\mathsf{alive}(Q^{a}_{I,\lambda})\) that cover or are to the right of \(t\). For simplicity, we need to express it more succinctly. Let  
\[\mathsf{alive}(\mathcal{C}_{I,\lambda,\kappa})=\bigcup\left\{\mathsf{alive}(Q ^{a}_{I,\lambda})\mid Q^{a}_{I,\lambda}\in\mathcal{C}_{I,\lambda,\kappa}\right\}\]  
be the set of nodes currently in \(\mathcal{C}_{I,\lambda,\kappa}\). Define \(\mathsf{dead}(\mathcal{C}_{I,\lambda,\kappa})\) and \(\mathsf{node}(\mathcal{C}_{I,\lambda,\kappa})\) similarly. For any item \(a\) and any subset \(X\subseteq\mathsf{node}(\mathcal{C}_{I,\lambda,\kappa})\), let \(X^{a}\) be the set of nodes in \(X\) that are monitoring \(a\) (and thus are the nodes from \(Q^{a}_{I,\lambda}\)). For any \(t\in I\), let \(X_{\geq t}\) denote the set of nodes in \(X\) that cover or are to the right of \(t\). Define \(v(X)=\sum_{N\in X}v(N)\) and \(d(X)=\sum_{N\in X}d(N)\). Then, \(\hat{f}_{a}([t,r_{I}])\) can be expressed as follows:  
\[\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t})=v( \mathsf{alive}(\mathcal{C}_{I,\lambda,\kappa})_{\geq t}^{a})\]  
The following theorem analyzes its accuracy, as well as gives the size of \(\mathcal{C}_{I,\lambda,\kappa}\). **Lemma 3**: _For any \(t\in I\), \(f_{a}([t,r_{I}])-\frac{1}{\kappa}f_{*}(I)\leq\hat{f}_{a}([t,r_{I}])\leq f_{a} ([t,r_{I}])+\lambda\log W\). Furthermore, \(\mathcal{C}_{I,\lambda,\kappa}\) has size \(O(f_{*}(I)/\lambda+\kappa)\) words._  
_Proof_ Recall that \(\hat{f}_{a}([t,r_{I}])=v(\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t})\). Consider any node \(N\in\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t}\). Note that \(v(N)=\sum_{J\in\mathcal{I}(N)}v_{\mathsf{add}}(N,J)\) where \(v_{\mathsf{add}}(N,J)\) is the value added to \(v(N)\) during the period when \(i(N)=J\). By Fact 2, we can divide it as \(v(N)=\sum\{v_{\mathsf{add}}(N,J)\mid J\text{ covers }t\}+\sum\{v_{\mathsf{add}}(N,J)\mid J\text{ is to the right of }t\}\). It follows that  
\[v(\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t}) =\sum_{N\in\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t}}v(N)\] \[=\sum_{N\in\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t}}\sum\{v_{ \mathsf{add}}(N,J)\mid J\text{ covers }t\}+\] \[\sum_{N\in\mathsf{alive}(Q^{a}_{I,\lambda})_{\geq t}}\sum\{v_{ \mathsf{add}}(N,J)\mid J\text{ is to the right of }t\} \tag{5}\]  
Figure 2: Interesting intervals for \(I=[1,8]\). Note that \(\sum_{N\in\mathsf{A}\mathsf{I}\mathsf{A}\mathsf{I}\mathsf{W}}(Q^{a}_{I,\lambda})_{ \geq t}\sum\big{\{}v_{\mathsf{add}}(N,J)\ \mid\ J\text{ is to the right of }t\big{\}}\ \leq\ f_{a}([t,r_{I}])\), because if an arrived item \((a,u)\) causes an increase of \(v_{\mathsf{add}}(N,J)\) for some \(J\) that is to the right of \(t\), then \(u\) must be in \([t,r_{I}]\). By Equation (5), to show the second inequality of the lemma, it suffices to show that \(S_{o}=\sum_{N\in\mathsf{A}\mathsf{I}\mathsf{W}}(Q^{a}_{I,\lambda})_{\geq t} \sum\big{\{}v_{\mathsf{add}}(N,J)\mid J\text{ covers }t\big{\}}=v_{\mathsf{add}}(N_{1},J_{1})+v_{\mathsf{add}}(N_{2},J_{2})+ \cdots+v_{\mathsf{add}}(N_{k},J_{k})\) is no greater than \(\lambda\log W\), as follows. Without loss of generality, suppose \(|J_{1}|\geq|J_{2}|\geq\cdots\geq|J_{k}|\). It can be verified that once an interval \(J\) is assigned to a node, it will not be assigned to other nodes; thus the \(J_{i}\)'s are distinct.