Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

How to find the median (or approximate median) of n chunks of values. The values in each chunk can be assumed to have been sorted if it helps. In addition, the existence of a histogram for each chunk is allowed.

share|improve this question
4  
Reading your question literally, the answer is: ignore the subsetting of your data into chunks, and simply take the median of the entire pooled dataset. Perhaps I am misunderstanding the question. Can you not simply take the median of the set of all values in your dataset? Why does it matter that the data are in "chunks"? Is there some part of this structure that you hope to preserve? –  Arthur Small Dec 18 '12 at 3:45
    
Are you saying that your values are somehow aggregated? In what format are your data? –  AdamO Apr 17 '13 at 18:06
add comment

1 Answer

I first assume you do not have the possibility to save all chunks and just compute the median from all values. If you do but the values are un ordered I would recommend a selection algorithm to find the median, see Selection algorithm (wikipedia).

I also assume that the chunks don't contain elements in some sequential order such that the smallest elements come in one chunk and then the larger in the next etc. At which case you only need to find the median in the middle chunk.

I think you're looking for some kind of recursive estimator of the median but to find a good estimator for this is hard. I would recommend to use some kind of frequency count which you update for each new chunk of data giving you the possibility to get the median using these counts. Depending on the amount of possible values this might become unfeasible in terms of space. But depending on the data structure used you should be able to do this for most cases.

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.