Find running median from a stream of integers

Re:Find running median from a stream of integers by notaddicted on Monday May 21, 2012 @06:05PM (#4005158)

This is kind of a weird problem, because it requires you to keep all the numbers in memory, so the "streaming" aspect is a lot less useful. And then once you have the list in memory there are linear median finding algorithms. The only way out that I can see is if you expect the incoming data to follow a normal distribution you can short-circuit the entire problem and just calculate the mean.

EDIT: One could construct a "Counted B-Tree" which is a pretty straightforward augmentation of the B-Tree (quick google result: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtre...). The insertion cost would still be of complexity log(n), the median could also be retrieved cheaply, and the data is kept sorted, but it takes more space.

[ Parent | on HN ]

Re:Find running median from a stream of integers by mturmon on Monday May 21, 2012 @10:16PM (#4005963)

You're right, it's kind of asking the wrong question.

Because of the robustness properties of the median, it would be hard to argue that the first 1E6 samples weren't enough, and that you really need to hang on for the next 9E6 to get an accurate median.

In real problems, if you have that much data, you would more likely start to question the iid assumption anyway, and you'd start looking for drifts in the medians within sliding windows. Real problems being real problems, you'd probably find some drift, and this would point out the unhelpfulness of an "all-data" median. ("Since the data is drifting, what is this the median of?")

[ Parent | on HN ]

Re:Find running median from a stream of integers by mbell697 on Monday May 21, 2012 @06:25PM (#4005221)

Depending on the application, you could keep a limited number of samples in memory and "below" or "above" those samples would simply be a counter of how many samples fall into either range. This would only work for applications where you expected the median to only vary in a limited fashion, and only after the system had been "primed".

For example, at any point in time, only store 100-1000 samples in memory, tree'd into "greater than median" and "less than median", additionally in each side of the tree store the number of samples that are in that tree but were purged do to the samples in memory requirement. When each new sample comes in, balance the tree to find the median.

I think this would work as long as a the median didn't have drastic movements up or down e.g. 1000 samples in a row < median, if that happened, it would exhaust your in memory sample set and you'd run out of samples to use as the median.

Even if you did expect wide variations you could use a similar approach but instead of purging samples into a counter you could serialize them to disk, or even have 3 layers, memory -> disk -> purge to counter.

EDIT: now that I think about this for more than 10 seconds, you may need to track the first derivative of median movement to determine how many samples to keep on a given side also.

[ Parent | on HN ]