An Optimal Algorithm for Sliding Window Order Statistics

The paper addresses the problem of computing the $k$-th smallest element in a sliding window of size $m$ over a data stream. While maximum and minimum can be updated in $O(1)$ and the median requires $O(\log m)$ per step, the author closes the gap by presenting an algorithm that runs in $O(\log k)$ time with $O(m)$ space, and proves this bound to be optimal.

The model assumes a stream of unique elements (duplicates can be disambiguated by indexing). A sliding window algorithm exposes an update-window interface that reads a new element and outputs the $k$-th smallest among the last $m$ elements. The key data structure is the augmented weight-balanced binary search tree (AWBBS), supporting insertion, deletion, and rank queries in $O(\log n)$.

Algorithm design.
A naive approach is to maintain all $m$ elements in a balanced tree, giving $O(\log m)$ per step. A refinement idea—keeping only the $k$ smallest elements—fails due to difficulty of handling deletions. The final design splits the stream into three blocks of size $m/2$: $B_\text{left}$, $B_\text{middle}$, $B_\text{right}$, overlapping with the current window as $W_\text{left}$, $W_\text{middle}$, $W_\text{right}$. For each block, the algorithm maintains a tree ($T_\text{left}$, $T_\text{middle}$, $T_\text{right}$) containing only the $k$ smallest elements. The $k$-th smallest overall is obtained by a specialized procedure find-rank-three-trees applied to these three trees.

Updating works as follows:

• $T_\text{right}$ is maintained directly, inserting each new element and discarding the maximum if size exceeds $k$.
• $T_\text{middle}$ is simply reassigned from $T_\text{right}$ every $m/2$ steps.
• $T_\text{left}$ is more complex: during preparation, for each possible shift of $B_\text{middle}$ an auxiliary array of “max” values is recorded to allow reverting between successive $k$-smallest sets. When $B_\text{middle}$ becomes $B_\text{left}$, these stored values allow maintaining $T_\text{left}$ efficiently as elements expire.

Algorithm 1 formalizes this update process. Each update executes only a bounded number of tree operations (at most three insertions and deletions, plus a few maxima). With AWBBS trees of size $k$, this yields $O(\log k)$ per update.

Correctness and complexity.
Lemmas show that at any point $T_\text{left}$, $T_\text{middle}$, and $T_\text{right}$ indeed hold the $k$ smallest elements of their respective segments. Combining them yields the correct $k$-th statistic. The time per update is $O(\log k)$ and space is $O(m)$. Careful pointer management ensures that block array reassignments are $O(1)$.

Lower bound.
A reduction from the problem to $k$-piecewise sorting proves that any algorithm must take $\Omega(\log k)$ per update in the comparison model. Thus the presented algorithm is asymptotically optimal.

Conclusion.
The algorithm unifies the spectrum of sliding window order statistics:

• $k=1$ gives the known $O(1)$ min/max updates.
• $k=m/2$ gives the median in $O(\log m)$.
• Arbitrary $k$ runs in $O(\log k)$, which is tight.

The work provides both an explicit construction and a matching lower bound, establishing the optimal complexity for sliding window order statistics.

Reference

Raykov, Pavel. 2023. “An Optimal Algorithm for Sliding Window Order Statistics.”. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.ICDT.2023.5. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.5.

@inproceedings{raykov2023,
  doi = {10.4230/LIPICS.ICDT.2023.5},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.5},
  author = {Raykov, Pavel},
  keywords = {sliding window, order statistics, median, selection algorithms, Theory of computation → Sorting and searching},
  language = {en},
  title = {An Optimal Algorithm for Sliding Window Order Statistics},
  publisher = {Schloss Dagstuhl – Leibniz-Zentrum für Informatik},
  year = {2023},
  copyright = {Creative Commons Attribution 4.0 International license}
}