# 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.

• 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. Feb 15, 2013 at 17:54
• 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. Feb 15, 2013 at 17:57
• 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. Apr 24, 2013 at 9:12

## 1 Answer

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.