## 3 A Simple Data Structure For Frequency Estimation
Furthermore, if \(v(Q^{a}_{I,\lambda})=d(Q^{a}_{I,\lambda})\), then \(v(N)=d(N)\) for every node \(N\) in \(Q^{a}_{I,\lambda}\). To maintain \((*)\), \(\mathcal{C}_{I,\lambda,\kappa}\) processes a newly arrived item \((a,u)\) with \(u\in I\) as follows. Figure 1: Suppose that \(\lambda=4\). (i) shows the queue \(Q^{a}_{I,\lambda}\) before the arrivals of items \((a,1),(a,2),(a,3),(a,8)\); (ii) is the resulting queue after the updates for these items; (iii) shows that after the arrival of another item \((a,1)\), the first node in (ii) is updated and refined. It is easy to see that Invariant \((*)\) always holds: Initially the number \(m\) of non-trivial queues is zero, and \(m\) increases only when \(\text{Process}((a,u))\) is on some trivial \(Q^{a}_{I,\lambda}\); in such case \(v(Q^{a}_{I,\lambda})\) becomes \(1\) and \(d(Q^{a}_{I,\lambda})\) remains \(0\). If \(m\) becomes \(\kappa\) after this increase, we will debit, among other queues, \(Q^{a}_{I,\lambda}\) and its \(d(Q^{a}_{I,\lambda})\) becomes \(1\) too. It follows that \(v(Q^{a}_{I,\lambda})=d(Q^{a}_{I,\lambda})\), and Lines 4-5 will make \(Q^{a}_{I,\lambda}\) trivial and \(m\) becomes less than \(\kappa\) again. We are now ready to define \(\mathcal{C}_{I,\lambda,\kappa}\)'s estimate \(\hat{f}_{a}([t,r_{I}])\) of \(f_{a}([t,r_{I}])\) and analyze its accuracy. We need some definitions. For any interval \(J=[p,q]\) and any \(t\in I\), we say that \(J\)_covers_\(t\) if \(t\in[p,q]\), is _to the right_ of \(t\) if \(t<p\), and is _to the left_ of \(t\) otherwise. For any item \(a\) and any \(t\in I=[\ell_{I},r_{I}]\), \(\mathcal{C}_{I,\lambda,\kappa}\)'s estimate of \(f_{a}([t,r_{I}])\) is  
\(\hat{f}_{a}([t,r_{I}])=\) the value sum of the nodes \(N\) currently in \(Q^{a}_{I,\lambda}\) whose \(i(N)\) covers or is to the right of \(t\). For example, in Figure 1, after the update of the last item \((a,1)\), we can obtain the estimate \(\hat{f}_{a}([2,8])=0+4+5=9\). Given any node \(N\) of \(Q^{a}_{I,\lambda}\), we say that \(N\) is monitoring \(a\) over \(J\), or simply \(N\) is monitoring \(J\) if \(i(N)=J\). Note that a node may monitor different intervals during different periods of execution, and the size of these intervals are monotonically decreasing. Observe that although there are about \(W^{2}/2\) possible sub-intervals of size-\(W\) interval \(I\), there are only about \(2W\) of them that would be monitored by some nodes: there is only one such interval of size \(W\), namely \(I=[\ell_{I},r_{I}]\), which gives birth to two such intervals of size \(W/2\), namely \([\ell_{I},m]\) and \([m+1,r_{I}]\) where \(m=\lfloor(\ell_{I}+r_{I})/2\rfloor\), and so on. We call these \(O(W)\) intervals _interesting intervals_. For any two interesting intervals \(J\) and \(H\) such that \(J\subset H\), we say that \(J\) is a _descendant_ of \(H\), and \(H\) is an _ancestor_ of \(J\). Figure 2 shows all the interesting intervals for \(I=[1,8]\), as well as their ancestor-descendant relationship. The following important fact is easy to verify by induction. **Fact 1**: _Any two interesting intervals \(J\) and \(H\) do not cross, although one can contain another, i.e., either \(J\subset H\), or \(H\subset J\), or \(J\cap H=\emptyset\). Furthermore, any interesting interval has at most \(\log W\) ancestors._For any node \(N\), let \(\mathcal{I}(N)\) be the set of intervals that have been monitored by \(N\) so far. The following fact can be verified from the update procedure. **Fact 2**: _Consider a node \(N\) in \(Q^{a}_{I,\lambda}\), where \(i(N)=J\)._  
* _If_ \(J\) _covers or is to the right of_ \(t\)_, then all intervals in_ \(\mathcal{I}(N)\) _cover or are to the right of_ \(t\)_._
* _If_ \(J\) _is to the left of_ \(t\)_, then all intervals in_ \(\mathcal{I}(N)\) _are to the left of_ \(t\)_._  
We say that \(N\) _covers or is to the right of_ \(t\) if the intervals in \(\mathcal{I}(N)\) cover or are to the right of \(t\); otherwise, \(N\) is _to the left of_ \(t\).