# Online approximation algorithm for median?

Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $$k$$ elements of a stream $$c_1,c_2,c_3,\dots$$?

The scenario is: I have a stream of numbers, and at any point in the streaming process I should be able to query for the (approximate) median in the last $$k$$ elements.

Thanks!

• Are your numbers bounded (both from below and from above)? This way, for each guess $minValue \cdot (1 + \epsilon)^k$ (up to $maxValue$), you can count how many items are smaller and how many are greater than the guess. Total memory is $O(\frac {\log n \log \frac {maxValue} {minValue}} {\epsilon})$. Here $\log n$ comes from the fact that for each guess we need to keep a count, and the rest is $\log_{1 + \epsilon} {\frac {maxValue} {minValue}}$
– user114966
Mar 20, 2021 at 2:52
• Please be explicit about the notion of Online approximation / streaming algorithm to use for this question - is storage required a concern, do soft or hard limits exist on effort spent per input? Mar 20, 2021 at 4:56

The algorithm you are searching for is Algorithm 1 in the paper. It uses just one unit of space to store the variable. Another, more accurate algorithm, uses two units of space and is shown in the paper as Algorithm 3. Algorithm 1 works as follows. Initialize a variable $$m$$ related to the estimated value of the median to zero. For each incoming stream item $$x$$, if $$x > m$$ then increase $$m$$ by one, otherwise decrement $$m$$ by one. Despite its simplicity, the analysis shows that the algorithm is quite effective.
If you need the exact median, store the last $$k$$ elements in a self-balancing binary search tree. Also keep a linked list of the last $$k$$ elements. At each time step you can delete the oldest element (the list will tell you which one) from the tree, then insert the newest one into the tree. It is easy to obtain the median from the tree in $$O(\log k)$$ time. Thus, you will do $$O(\log k)$$ work at each time step, and you will need $$k$$ space.
If you want to use much less than $$k$$ space, and are satisfied with the approximate median (you don't need the exact value), you can use various methods for approximating a streaming histogram.