## 2 Preliminaries  
Our data structures for the frequent item set problem depends on data structures for the following two related data stream problems. Let \(0<\epsilon<1\) be any real number, and \(\tau_{\text{cur}}\) be the current time. * The \(\epsilon\)_-approximate basic counting_ problem asks for data structure that allows us to obtain, for any interval \(I=[\tau_{\text{cur}}-W^{\prime}+1,\tau_{\text{cur}}]\) where \(W^{\prime}\leq W\), an estimate \(\hat{f}_{*}(I)\) of \(f_{*}(I)\) such that \(|\hat{f}_{*}(I)-f_{*}(I)|\leq\epsilon f_{*}(I)\). * The \(\epsilon\)_-approximate counting_ problem asks for data structure that allows us to obtain, for any item \(a\) and any interval \(I=[\tau_{\text{cur}}-W^{\prime}+1,\tau_{\text{cur}}]\) where \(W^{\prime}\leq W\), an estimate \(\hat{f}_{a}(I)\) of \(f_{a}(I)\) such that \(|\hat{f}_{a}(I)-f_{a}(I)|\leq\epsilon f_{*}(I)\). As mentioned in Section 1, [PERSON] _et al._[1] gave an \(O(\frac{1}{\epsilon}\log W\log(\frac{\epsilon B}{\log W}))\)-space data structure \(\mathcal{B}_{\epsilon}\) for solving the \(\epsilon\)-approximate basic counting problem. In this paper, we give an \(O(\frac{1}{\epsilon}\log W\log(\frac{\epsilon B}{\log W})\log\log W)\)-space data structure \(\mathcal{D}_{\epsilon}\) for solving the harder \(\epsilon\)-approximate counting problem. The theorem below shows how to use these two data structures to answer \(\epsilon\)-approximate frequent item set query. **Theorem 1**: _Let \(\epsilon_{o}=\epsilon/4\). Given \(\mathcal{B}_{\epsilon_{o}}\) and \(\mathcal{D}_{\epsilon_{o}}\), we can answer any \(\epsilon\)-approximate frequent item set query. The total space required is \(O(\frac{1}{\epsilon}\log W\log(\frac{\epsilon B}{\log W})\log\log W)\)._  
Proof: The space requirement is obvious. Consider any \(\epsilon\)-approximate frequent item set query \((\phi,W^{\prime})\) where \(\epsilon\leq\phi\leq 1\) and \(W^{\prime}\leq W\). Let \(I=[\tau_{\text{cur}}-W^{\prime}+1,\tau_{\text{cur}}]\). Since \(\epsilon_{o}=\epsilon/4\), the estimates given by \(\mathcal{B}_{\epsilon_{o}}\) satisfy \(|\hat{f}_{*}(I)-f_{*}(I)|\leq\frac{\epsilon}{4}f_{*}(I)\), and for any item \(a\), the estimates given by \(\mathcal{D}_{\epsilon_{o}}\) satisfy \(|\hat{f}_{a}(I)-f_{a}(I)|\leq\frac{\epsilon}{4}f_{*}(I)\). To answer the query \((\phi,W^{\prime})\), we return the set  
\[S_{\phi}=\{a\mid\hat{f}_{a}(I)\geq(\phi-\frac{\epsilon}{2})\hat{f}_{*}(I)\}\]which satisfies the required conditions (C1) and (C2) because  
* for any item \(a\) with \(f_{a}(I)\geq\phi f_{*}(I)\), \(\hat{f}_{a}(I)\geq f_{a}(I)-\frac{\epsilon}{4}f_{*}(I)\geq(\phi-\frac{\epsilon}{ 4})f_{*}(I)\geq(\phi-\frac{\epsilon}{4})(\frac{1}{1+\frac{\epsilon}{4}})\hat{f}_ {*}(I)\geq(\phi-\frac{\epsilon}{4})(1-\frac{\epsilon}{4})\hat{f}_{*}(I)\geq( \phi-\frac{\epsilon}{2})\hat{f}_{*}(I),\) and \(a\in S_{\phi}\); thus (C1) is satisfied, and
* for every \(a\in S_{\phi}\), we have \(f_{a}(I)\geq\hat{f}_{a}(I)-\frac{\epsilon}{4}f_{*}(I)\geq(\phi-\frac{\epsilon} {2})\hat{f}_{*}(I)-\frac{\epsilon}{4}f_{*}(I)\geq(\phi-\frac{\epsilon}{2})(1- \frac{\epsilon}{4})f_{*}(I)-\frac{\epsilon}{4}f_{*}(I)\geq(\phi-\epsilon)f_{*} (I);\) thus (C2) is satisfied. The building block of \(\mathcal{D}_{\epsilon}\) is a data structure that counts items over some fixed interval (instead of the sliding window).