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

2 Answers 2

2
$\begingroup$

There is an incredibly simple to implement algorithm available in Qiang Ma, S. Muthukrishnan, Mark Sandler. Frugal Streaming for Estimating Quantiles:One (or two) memory suffices. CoRR abs/1407.1121 (2014)

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.

Of course much better algorithms for tracking not just the median but all of the quantiles exist. Among the latest relative-error approximation algorithms, you can take into account DDSKETCH and UDDSKETCH (implemented and used by TimescaleDB). The source code for both is freely available (e.g., this is the UDDSKETCH repository).

$\endgroup$
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 and acknowledge you have read our privacy policy.

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