Nontrivial algorithm for computing a sliding window median I need to calculate the running median:


Input: $n$, $k$, vector $(x_1, x_2, \dotsc, x_n)$.
Output: vector $(y_1, y_2, \dotsc, y_{n-k+1})$, where $y_i$ is the median of $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$.


(No cheating with approximations; I would like to have exact solutions. Elements $x_i$ are large integers.)

There is a trivial algorithm that maintains a search tree of size $k$; the total running time is $O(n \log k)$. (Here a "search tree" refers to some efficient data structure that supports insertions, deletions, and median queries in logarithmic time.)

However, this seems a bit stupid to me. We will effectively learn all order statistics within all windows of size $k$, not just the medians. Moreover, this is not too attractive in practice, especially if $k$ is large (large search trees tend to be slow, overhead in memory consumption is non-trivial, cache-efficiency is often poor, etc.).

Can we do anything substantially better?

Are there any lower bounds (e.g., is the trivial algorithm asymptotically optimal for the comparison model)?



Edit: David Eppstein gave a nice lower bound for the comparison model! I wonder if it is nevertheless possible to do something slightly more clever than the trivial algorithm?

For example, could we do something along these lines: divide the input vector to parts of size $k$; sort each part (keeping track of the original positions of each element); and then use the piecewise sorted vector to find the running medians efficiently without any auxiliary data structures? Of course this would still be $O(n \log k)$, but in practice sorting arrays tends to be much faster than maintaining search trees.



Edit 2: Saeed wanted to see some reasons why I think sorting is faster than search tree operations. Here are very quick benchmarks, for $k = 10^7$, $n = 10^8$:


≈ 8s: sorting $n/k$ vectors with $k$ elements each
≈ 10s: sorting a vector with $n$ elements
≈ 80s: $n$ insertions &amp; deletions in a hash table of size $k$
≈ 390s: $n$ insertions &amp; deletions in a balanced search tree of size $k$


The hash table is there just for comparison; it is of no direct use in this application.

In summary, we have almost a factor 50 difference in the performance of sorting vs. balanced search tree operations. And things get much worse if we increase $k$.

(Technical details: Data = random 32-bit integers. Computer = a typical modern laptop. The test code was written in C++, using the standard library routines (std::sort) and data structures (std::multiset, std::unsorted_multiset). I used two different C++ compilers (GCC and Clang), and two different implementations of the standard library (libstdc++ and libc++). Traditionally, std::multiset has been implemented as a highly optimised red-black tree.)
Here's a lower bound from sorting. Given an input set $S$ of length $n$ to be sorted, create an input to your running median problem consisting of $n-1$ copies of a number smaller than the minimum of $S$, then $S$ itself, then $n-1$ copies of a number larger than the maximum of $S$, and set $k=2n-1$. The running medians of this input are the same as the sorted order of $S$.

So in a comparison model of computation, $\Omega(n\log n)$ time is required. Possibly if your inputs are integers and you use integer sorting algorithms you can do better.