Sliding window order statistics in sublinear space

Abstract

We extend the multi-pass streaming model to sliding window problems, and address the problem of computing order statistics on fixed-size sliding windows, in the multi-pass streaming model as well as the closely related communication complexity model. In the $2$-pass streaming model, we show that on input of length $N$ with values in range $[0,R]$ and a window of length $K$, sliding window minimums can be computed in $\tilde{O}(\sqrt{N})$. We show that this is nearly optimal (for any constant number of passes) when $R\ge K$, but can be improved when $R=o(K)$ to $\tilde{O}(\sqrt{NR/K})$. Furthermore, we show that there is an $(l+1)$-pass streaming algorithm which computes $l^{\text{th}}$-smallest elements in $\tilde{O}(l^{3/2}\sqrt{N})$ space. In the communication complexity model, we describe a simple $\tilde{O}(p{N}^{1/p})$ algorithm to compute minimums in $p$ rounds of communication for odd $p$, and a more involved algorithm which computes the $l^{\text{th}}$-smallest elements in $\tilde{O}(p{l}^2{N}^{1/(p-2l-1)})$ space. Finally, we prove that the majority statistic on boolean streams cannot be computed in sublinear space, implying that $l^{\text{th}}$-smallest elements cannot be computed in space both sublinear in $N$ and independent of $l$.