# 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 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 at 4:56

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.