undefined | Better HN

0 pointskingfishr12y ago0 comments

Oh, that'll be great! That's not quite the same as a sliding window of last 5 minutes, but it'll definitely work for my use case.

(Intuitively, a sliding window seems very hard/impossible -- how do you discard old events without keeping a complete record?)

0 comments

teraflop12y ago

There are other algorithms that handle the sliding-window case, e.g. http://research.microsoft.com/pubs/77611/quantiles.pdf

But for all but the most extreme cases, it's sufficient to just keep all the values in memory until they fall out of your window. Even if you're getting 1000 requests/second, that's still only 300,000 values that you have to store.

bmizerany12y ago

There may be a way to implement this in perks/quantiles by adding another piece of metadata for the timestamp. There is a space cost for this, but it may be okay or even opt-in. Maybe I'll look into this soon.

Edit:

I do agree that if you're working with datasets that fit in memory, you're probably better off keeping all the samples to find your percentile and not using this package. In fact, perks will not compress for datasets under 500 values.

jcrites12y ago

I have seen continuous exponential decay applied to this problem.

j / k navigate · click thread line to collapse