3
$\begingroup$

I am looking for an efficient algorithm to find streaming data median. Median is described as the numerical value separating the higher half of a sample, a population, or a probability distribution, from the lower half.

We have stream of data in our system like 1, 10, -40, 20, 2, 6,.....Our task is find median of data as they arrive.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Perhaps this would be of use: stackoverflow.com/questions/1387497/… I think "online" rather than "streaming" would be more efficient in searching for an answer to this. $\endgroup$ – Shaull Feb 15 '13 at 17:54
  • 3
    $\begingroup$ If you can store the stream of data as it comes in, the two-heap approach can be used. If you cannot store, I think you will only be able to find the approximate median. $\endgroup$ – Paresh Feb 15 '13 at 17:57
  • $\begingroup$ Further to the comment of Paresh, to find the exact median in the worst case requires storing half of the input numbers. The answers at SO discuss the solution using two heaps to keep track of the values below and above the median so far, which requires storing all the numbers. $\endgroup$ – András Salamon Apr 24 '13 at 9:12
3
$\begingroup$

You can find the median approximately with this: Approximate Medians and other Quantiles in One Pass and With Limited Memory, to some degree of confidence. That algorithm works, but it's pretty slow. One of the authors of that paper, Gurmeet Manku, has some other publications that might be what you're looking for, also.

There's a stackoverflow question that seems relevant.

Improve this answer
$\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.