Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Shaull Feb 15 '13 at 17:54
3  
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. –  Paresh Feb 15 '13 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. –  András Salamon Apr 24 '13 at 9:12
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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