1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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}}$ $\endgroup$
    – user114966
    Mar 20 at 2:52
  • $\begingroup$ 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? $\endgroup$
    – greybeard
    Mar 20 at 4:56
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.