## 5 Reducing the Size of \(\mathcal{D}^{Y}_{I,\epsilon}\)
6 Further Reducing the Size of \(\mathcal{D}^{Y}_{I,\epsilon}\) for Streams with Small Tardiness  
Recall that in an out-of-order data stream with _tardiness_\(d_{\max}\in[0,W]\), any item \((a,u)\) arriving at time \(\tau_{\text{cur}}\) satisfies \(u\geq\tau_{\text{cur}}-d_{\max}\); in other words, the delay of any item is guaranteed to be at most \(d_{\max}\). This section extends \(\mathcal{D}^{Y}_{I,\epsilon}\) to a data structure \(\mathcal{E}^{Y}_{I,\epsilon}\) that takes advantage of this maximum delay guarantee to reduce the space usage. The idea is as follows. Since there is no new item with stamps smaller than \(\tau_{\text{cur}}-d_{\max}\), we will not make any further change to those nodes to the of left \(\tau_{\text{cur}}-d_{\max}\) and hence can consolidate these nodes to reduce space substantially. To handle those nodes with timestamps in \([\tau_{\text{cur}}-d_{\max},\tau_{\text{cur}}]\), we use the data structure given in Section 5; since it is monitoring an interval of \(d_{\max}\) instead of \(W\), its size is \(O(\frac{1}{\epsilon}(\log\log d_{\max})\log d_{\max})\) instead of \(O(\frac{1}{\epsilon}(\log\log W)\log W)\). To implement \(\mathcal{E}^{Y}_{I,\epsilon}\), we need a new operation called _consolidate_. Consider any list of queues \(\langle Q^{a}_{J_{1},\lambda},Q^{a}_{J_{2},\lambda},\ldots,Q^{a}_{J_{m},\lambda}\rangle\), where \(J_{1},J_{2},\ldots,J_{m}\) are ordered from left to right and form a partition of the interval \(J_{1..m}=J_{1}\cup\cdots\cup J_{m}\). We consolidate them into a single queue \(Q^{a}_{J_{1..m},\lambda}\) as follows:  
1. Concatenate the queues into a single queue, in which the nodes preserve the left-right order. 2. Starting from the leftmost node, check from left to right every node \(N\) in the queue, if \(N\) is not the rightmost node and \(v(N)<\lambda\), merge it with the node \(N^{\prime}\) immediately to its right, _i.e._, delete \(N\), set \(v(N^{\prime})=v(N)+v(N^{\prime})\), \(d(N^{\prime})=d(N)+d(N^{\prime})\) and \(\mathcal{I}(N^{\prime})=\mathcal{I}(N)\cup\mathcal{I}(N^{\prime})\). Note that after the consolidation, the resulting queue \(Q^{a}_{J_{1..m},\lambda}\) has at most one node (the rightmost one) with value smaller than \(\lambda\). Given the list \(\langle\mathcal{C}_{J_{1},\lambda,\kappa(c_{1})},\ldots,\mathcal{C}_{J_{m}, \lambda,\kappa(c_{m})}\rangle\), we consolidate them into \(\mathcal{C}_{J_{1..m},\lambda,\frac{1}{\epsilon}}\) by first consolidating, for each item \(a\), the queues \(Q^{a}_{J_{1},\lambda},\ldots,Q^{a}_{J_{m},\lambda}\) in \(\mathcal{C}_{J_{1},\lambda,\kappa(c_{1})},\ldots,\mathcal{C}_{J_{m},\lambda, \kappa(c_{m})}\) into the queue \(Q^{a}_{J_{1..m},\lambda}\) and put it in \(\mathcal{C}_{J_{1..m},\lambda,\frac{1}{\epsilon}}\). Then, we apply Lines 3-5 of procedure \(\text{Process}(\,)\) repeatedly to reduce the number of non-trivial queues in the data structure to \(\frac{1}{\epsilon}\). We are now ready to describe how to extend \(\mathcal{D}^{Y}_{I,\epsilon}\) to \(\mathcal{E}^{Y}_{I,\epsilon}\). In our discussion, we fix \(\lambda=\frac{\epsilon Y}{\log d_{\max}}\), and without loss of generality, we assume that \(I=[1,W]\). Recall that \(p_{\text{max}}\) denotes the largest timestamp in \(I\) such that \(\hat{f}_{*}([p_{\text{max}},r_{I}])>(1+\epsilon)Y\) (which implies \(f_{*}([p_{\text{max}},r_{I}])>Y\)). We partition \(I\) into sub-windows \(I_{1},I_{2},\ldots,I_{m}\), each of size \(d_{\max}\) (_i.e._, \(I_{i}=[(i-1)d_{\max},id_{\max}]\)). We divide the execution into different periods according to \(\tau_{\text{cur}}\), the current time. * During the \(1\)st period, when \(\tau_{\text{cur}}\in[1,d_{\max}]=I_{1}\), \(\mathcal{E}^{Y}_{I,\epsilon}\) simply is \(\mathcal{D}^{Y}_{I_{1},\epsilon}\). * During the \(2\)nd period, when \(\tau_{\text{cur}}=I_{2}\), \(\mathcal{E}^{Y}_{I,\epsilon}\) maintains \(\mathcal{D}^{Y}_{I_{2},\epsilon}\) in addition to \(\mathcal{D}^{Y}_{I_{1},\epsilon}\).