Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Find running median from a stream of integers

stackoverflow.com

Post reply on HN
Print view View original

21–29 of 29 posts

Re: Find running median from a stream of integers

#21

Post by sesqu »

yummyfajitas wrote: post #16
dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. I'm not sure what proof you have in mind, but I don't think using the word "converge" is correct. Near as I can tell, your algorithm is x[n+1]= x[n] + sign(sample[n]-x[n]). If you are applying the c.l.t. to sign(sample[n]-x[n]), all this says is that your algo…

It's worth stressing that while the c.l.t. gives a reasonable justification to using that algorithm for the mean, that justification does not extend to the median, which can diverge from the mean by as much as range/2. You'd need to be able to assume something like a connected set.

Re: Find running median from a stream of integers

#22

Post by raymondh »

Too bad that a horrible answer was selected as the best. The minheap/maxheap solution requires that the entire stream of integers be stored in memory.

There is a fast and memory efficient solution using Indexable Skiplists: http://code.activestate.com/recipes/576930-efficient-running...

In a n-sized sliding window, only the most recent n elements need to be stored (not the entire data stream). The skiplist insertions, deletions, and indexed lookups are all O(log n).

Re: Find running median from a stream of integers

#23

Post by toemetoch »

derleth wrote: post #14
bjornsing wrote: post #8

Earlier quoted context omitted.

> It is easy to prove that... Reminds me of a similar comment in the margin of a old book: http://en.wikipedia.org/wiki/Fermats_Last_Theorem . :) But it does sound both plausible and brilliant. How do you prove it (in broad terms)?

toemetoch, who is dead, said: "In a normal distribution the probability of a value higher or lower than mean is 50%. So if you find mean, the average of your +1/-1 noise is zero -> if you're on mean you'll remain there. If you're not on mean you have a (50 + error)% chance of moving towards mean and (50 - error)% chance of moving away from mean on the next random value -> the trend is towards mean."

toemetoch, who is dead

... I'm not following. I can see my reply a few posts down. I accidentally hit submit twice, deleted one but the second one is still there.

Edit: The same technique can be found in some 1-bit ADCs, I believe it's delta-sigma ADC.

Re: Find running median from a stream of integers

#24

Post by [deleted] »

toemetoch wrote: post #23
derleth wrote: post #14

Earlier quoted context omitted.

toemetoch, who is dead, said: "In a normal distribution the probability of a value higher or lower than mean is 50%. So if you find mean, the average of your +1/-1 noise is zero -> if you're on mean you'll remain there. If you're not on mean you have a (50 + error)% chance of moving towards mean and (50 - error)% chance of moving away from mean on the next random value -> the trend is towards mean."

toemetoch, who is dead ... I'm not following. I can see my reply a few posts down. I accidentally hit submit twice, deleted one but the second one is still there. Edit: The same technique can be found in some 1-bit ADCs, I believe it's delta-sigma ADC.

[deleted]

Re: Find running median from a stream of integers

#25

Post by pg »

njs12345 wrote: post #15
bjornsing wrote: post #8

Earlier quoted context omitted.

> It is easy to prove that... Reminds me of a similar comment in the margin of a old book: http://en.wikipedia.org/wiki/Fermats_Last_Theorem . :) But it does sound both plausible and brilliant. How do you prove it (in broad terms)?

Slightly off topic, but looks like toemetoch has tripped one of the hellban filters, isn't a spammer, and has no contact info in his profile. Might want to sort that out if you're reading this toemetoch!

No, he just accidentally posted the same comment twice. The new one got autokilled. Then he deleted the first one, leaving a single dead comment.

Re: Find running median from a stream of integers

#26

Post by toemetoch »

njs12345 wrote: post #15
bjornsing wrote: post #8

Earlier quoted context omitted.

> It is easy to prove that... Reminds me of a similar comment in the margin of a old book: http://en.wikipedia.org/wiki/Fermats_Last_Theorem . :) But it does sound both plausible and brilliant. How do you prove it (in broad terms)?

Slightly off topic, but looks like toemetoch has tripped one of the hellban filters, isn't a spammer, and has no contact info in his profile. Might want to sort that out if you're reading this toemetoch!

Thanks for the info. Account seems to be normal again, mental state is not.

Re: Find running median from a stream of integers

#27

Post by derleth »

toemetoch wrote: post #23
derleth wrote: post #14

Earlier quoted context omitted.

toemetoch, who is dead, said: "In a normal distribution the probability of a value higher or lower than mean is 50%. So if you find mean, the average of your +1/-1 noise is zero -> if you're on mean you'll remain there. If you're not on mean you have a (50 + error)% chance of moving towards mean and (50 - error)% chance of moving away from mean on the next random value -> the trend is towards mean."

toemetoch, who is dead ... I'm not following. I can see my reply a few posts down. I accidentally hit submit twice, deleted one but the second one is still there. Edit: The same technique can be found in some 1-bit ADCs, I believe it's delta-sigma ADC.

Odd. I still only see one response from you with that content, and it is dead.

Re: Find running median from a stream of integers

#28

Post by tel »

yummyfajitas wrote: post #16
dude_abides wrote: post #6

Here is a clever algorithm to find the median of a stream of integers by using just one variable: The idea is to maintain a floating median. Start with an arbitrary number, say 0. If the incoming number is greater than the estimate, num += 1, else num -= 1. It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. Us…

It is easy to prove that for a large enough stream, assuming the stream is drawn from iid samples, this would converge to the median, by central limit theorem. I'm not sure what proof you have in mind, but I don't think using the word "converge" is correct. Near as I can tell, your algorithm is x[n+1]= x[n] + sign(sample[n]-x[n]). If you are applying the c.l.t. to sign(sample[n]-x[n]), all this says is that your algo…

Yeah, this is more Martingale territory than clt. I wrote a proof below that gives a limited Martingale property of the process, but I don't know enough further theory to continue. (slash I'm lazy and have better things to do)

Re: Find running median from a stream of integers

#29

Post by sixothree »

Drbble wrote: post #20
sixothree wrote: post #2

Heap sounds like overkill to find the middle value in a running list. What's wrong with simple stack and keeping track of how many integers you've received?

Your solution is for median position, not median value, and it would require a queue, not a stack, so unneeded old values could be dropped.

Of course, a queue is correct.
Post reply on HN