## 1 Introduction
### Technical Digest  
To solve the frequent item set problem, we need to estimate the frequency of any item with relative error \(\epsilon f_{*}(I)\) where \(I=[\tau_{\text{cur}}-W+1,\tau_{\text{cur}}]\) is the interval covered by the sliding window. To this end, we first propose a simple data structure for estimating the frequency of a fixed item over the sliding window. Then, we adapt a technique of [PERSON] and [PERSON] [14] to extend our data structure to handle any item. The result is an \(O(f_{*}(I))/\lambda)\)-space data structure that allows us to obtain an estimate for any item with an error bound of about \(\lambda\log W\). Here \(\lambda\) is a design parameter. To ensure \(\lambda\log W\) to be no greater than \(\epsilon f_{*}(I)\), we should set \(\lambda\leq\epsilon f_{*}(I)/\log W\). Since \(f_{*}(I)\) can be as small as \(\Theta(\frac{1}{\epsilon}\log W)\) (the case for smaller \(f_{*}(I)\) can be handled by brute-force), we need to be conservative and set \(\lambda\) to some constant. But then the size of the data structure can be \(\Theta(B)\) because \(f_{*}(I)\) can be as large as \(B\). To reduce space, we introduce a multi-resolution approach. Instead of using one single data structure, we maintain a collection of \(O(\log B)\) copies of our data structure, each uses a distinct, carefully chosen parameter \(\lambda\) so that it could estimate the frequent item set with sufficient accuracy when \(f_{*}(I)\) is in a particular range. The resulting data structure uses \(O(\frac{1}{\epsilon}\log W\log B)\) space. \begin{table}
\begin{tabular}{c l} \hline \hline \multicolumn{2}{c}{**Space Complexity (words)**} \\ \hline Synchronous [7] & \(O(\frac{1}{\epsilon}\log(\epsilon B))\) \\ Asynchronous [1] & \(O(\frac{1}{\epsilon}\log W\log(\frac{\epsilon B}{\log W})\min\{\log W,\frac{1} {\epsilon}\}\log|U|)\) \\ Asynchronous [\(\dagger\)] & \(O(\frac{1}{\epsilon}\log W\log(\frac{\epsilon B}{\log W})\log\log W)\) \\ Asynchronous & \(O(\frac{1}{\epsilon}\log d_{\max}\log(\frac{\epsilon B}{\log d_{\max}})\log \log d_{\max})\) \\ with tardiness [\(\dagger\)] & \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The space complexity for answering \(\epsilon\)-approximate frequent item set query in a sliding time window. Results from this paper are marked with [\(\dagger\)]. Note that we assume \(B\geq\frac{1}{\epsilon}\log W\); otherwise, we can always store all items in the window for exact answer, using \(O(\frac{1}{\epsilon}\log W)\) words. Similarly, for the result with tardiness, we assume \(B\geq\frac{1}{\epsilon}\log d_{\max}\). Unfortunately, a careful analysis of our data structure reveals that in the worst case, it can only guarantee estimates with an error bound of \(\epsilon f_{*}(H\cup I)\) where \(H=[\tau_{\text{cur}}-2W+1,\tau_{\text{cur}}-W]\), not the required \(\epsilon f_{*}(I)\). The reason is that the error of its estimates over \(I\) depend on the number of updates made during \(I\), and unlike synchronous data stream, this number for asynchronous data stream can be significantly larger than \(f_{*}(I)\). For example, at time \(\tau_{\text{cur}}-W+1\), there may still be many new items \((a,u)\) with timestamps \(u\in H\), for which we must update our data structure to get good estimates when the sliding window is at earlier positions. Indeed, the number of updates during \(I\) can be as large as \(f_{*}(H\cup I)\), and this gives an error bound of \(\epsilon f_{*}(H\cup I)\). To reduce the error bound to \(\epsilon f_{*}(I)\), we introduce a novel algorithm to split the data structure into independent smaller ones at appropriate times. For example, at time \(\tau_{\text{cur}}-W+1\), we can split our data structure into two smaller ones \(D_{H}\) and \(D_{I}\), and we will only update \(D_{H}\) for items \((a,u)\) with \(u\in H\) and update \(D_{I}\) for those with \(u\in I\). Then, when we need to find an estimate on \(I\) at time \(\tau_{\text{cur}}\), we only need to consult \(D_{I}\), and the number of updates made to it is \(f_{*}(I)\).