## 3 A Simple Data Structure For Frequency Estimation  
Let \(I=[\ell_{I},r_{I}]\) be any interval of size \(W\). To simplify notation, we assume that \(W\) is a power of \(2\), so that \(\log W\) is an integer and we can avoid the floor or the ceiling functions. In this section, we describe a simple data structure \(\mathcal{C}_{I,\lambda,\kappa}\) that enables us to obtain, for any item \(a\), a good estimate of \(a\)'s frequency over \(I\). The parameters \(\lambda\) and \(\kappa\) determine its accuracy and space usage. However, its accuracy is not enough for answering any \(\epsilon\)-approximate frequent item set query. We will explain how to improve the accuracy in the next section. Roughly speaking, \(\mathcal{C}_{I,\lambda,\kappa}\) is a set of queues \(Q^{a}_{I,\lambda}\), _i.e._, \(\mathcal{C}_{I,\lambda,\kappa}=\{Q^{a}_{I,\lambda}\ |\ a\in U\}\). For an item \(a\), the queue \(Q^{a}_{I,\lambda}\) keeps track of the occurrences of \(a\) in \(I\). Each node \(N\) in \(Q^{a}_{I,\lambda}\) is associated with an interval \(i(N)\), a value \(v(N)\), and a debit \(d(N)\); \(v(N)\) counts the number of arrived items \((a,u)\) with \(u\in i(N)\), and \(d(N)\) is for implementing a space reduction technique. Initially, \(Q^{a}_{I,\lambda}\) has only one node \(N\) with \(i(N)=I\), and \(v(N)=d(N)=0\). In general, \(Q^{a}_{I,\lambda}\) is a queue \(\langle N_{1},N_{2},\ldots,N_{k}\rangle\) of nodes whose intervals form a partition of \(I\), _i.e._,  
\[\langle i(N_{1}),i(N_{2}),\ldots,i(N_{k})\rangle=\langle[p_{1},q_{1}],[p_{2},q _{2}],\ldots,[p_{k},q_{k}]\rangle\]  
where \(q_{i-1}+1=p_{i}\leq q_{i}\) and \(\bigcup_{1\leq i\leq k}[p_{i},q_{i}]=I\). When an item \((a,u)\) with \(u\in I\) arrives, we update \(Q^{a}_{I,\lambda}\) as follows. ```
1: find the unique node \(N\) in \(Q^{a}_{I,\lambda}\) with \(u\in i(N)=J=[p,q]\);
2: increase the value of \(N\) by \(1\), _i.e._, \(v(N)=v(N)+1\);
3:if (\(|J|>1\)and\(\lambda\) units have been added to \(v(N)\) since \(J\) is assigned to \(i(N)\)) then
4: /* refine \(J\) */
5: create a new node \(N^{\prime}\) and insert it to the left of \(N\);
6: let \(i(N^{\prime})=[p,m]\), \(i(N)=[m+1,q]\) where \(m=\lfloor(p+q)/2\rfloor\);
7: let \(v(N^{\prime})=0\) and \(d(N^{\prime})=0\);
8: /* we make no change to \(v(N)\) and \(d(N)\)  */
9:endif
```  
Figure 1 gives an example on how \(Q^{a}_{I,\lambda}\) is updated using the procedure. Obviously, a direct implementation of \(\mathcal{C}_{I,\lambda,\kappa}\) uses too much space. We now extend a technique of [PERSON] and [PERSON] [14] to reduce the space requirement. For any \(Q^{a}_{I,\lambda}\), we say that \(Q^{a}_{I,\lambda}\) is _trivial_ if the queue contains only a single node \(N\) with (i) \(i(N)=I\), and (ii) \(v(N)=d(N)=0\). Every queue in \(\mathcal{C}_{I,\lambda,\kappa}\) is trivial initially. The key for reducing the space complexity of \(\mathcal{C}_{I,\lambda,\kappa}\) is to maintain the following invariant throughout the execution:  
* There are at most \(\kappa\) non-trivial queues in \(\mathcal{C}_{I,\lambda,\kappa}\). We call \(\kappa\) the _capacity_ of \(\mathcal{C}_{I,\lambda,\kappa}\). The invariant helps us save space because we do not need to store trivial queues physically in memory. To maintain \((*)\), each queue \(Q^{a}_{I,\lambda}\) supports the following procedure, which is called only when \(v(Q^{a}_{I,\lambda})\), the total values of the nodes in \(Q^{a}_{I,\lambda}\), is strictly greater than \(d(Q^{a}_{I,\lambda})\), the total debits of the nodes in \(Q^{a}_{I,\lambda}\). ```
1:if\(v(Q^{a}_{I,\lambda})\leq d(Q^{a}_{I,\lambda})\)) then
2: return error;
3:else
4: find an arbitrary node \(N\) of \(Q^{a}_{I,\lambda}\) with \(v(N)>d(N)\);
5: /\(*\) such a node must exist because \(v(Q^{a}_{I,\lambda})>d(Q^{a}_{I,\lambda})\) */
6: \(d(N)=d(N)+1\);
7:endif
```  
**Algorithm 1**\(\mathcal{Q}^{a}_{I,\lambda}\).Debit( )  
Note from the implementation of Debit( ) that \(v(Q^{a}_{I,\lambda})\) is always no smaller than \(d(Q^{a}_{I,\lambda})\), and for each node \(N\) of \(Q^{a}_{I,\lambda}\), \(v(N)\geq d(N)\).