Streaming Median

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.

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.

StackExchange Computer Science Q#9816, answer score: 3