Perks – Effectively compute quantiles for unbounded data streams
groups.google.com
Perks – Effectively compute quantiles for unbounded data streams
1–10 of 15 posts
Re: Perks – Effectively compute quantiles for unbounded data streams
#2This is a really awesome problem! I tackled this for my work at TempoDB and ended up going with the Q-Digest algorithm although I took a good look at CKMS. Really cool to see this implements merging streams, I remember reading that CKMS was more difficult to merge streams than Q-Digest.
If anyone is interested this was my write up for algorithm selection: http://blog.tempo-db.com/post/42318820124/estimating-percent...
Re: Perks – Effectively compute quantiles for unbounded data streams
#3This is a really awesome problem! I tackled this for my work at TempoDB and ended up going with the Q-Digest algorithm although I took a good look at CKMS. Really cool to see this implements merging streams, I remember reading that CKMS was more difficult to merge streams than Q-Digest. If anyone is interested this was my write up for algorithm selection: http://blog.tempo-db.com/post/42318820124/estimating-percent..…
Great post.
Distributing the computation was quite easy. I emailed the authors of the paper and they gave me a quick answer, which is what I implemented and tested.
I'm interested in adding more implementations of the problem to perks, like Q-Digest, along with other streaming data problems.
Re: Perks – Effectively compute quantiles for unbounded data streams
#4I don't really understand what this does, I didn't find a "for dummies" section on the site - can anyone give a real-world use case and (ideally) a comparison with some other system that does the same thing?
Re: Perks – Effectively compute quantiles for unbounded data streams
#5I don't really understand what this does, I didn't find a "for dummies" section on the site - can anyone give a real-world use case and (ideally) a comparison with some other system that does the same thing?
azmenthe's article covers the problem well: http://blog.tempo-db.com/post/42318820124/estimating-percent...
Basically, when you have more data than memory and time to sort them in order to find the percentile you're looking for, you need to employ an algorithm that trades rank selection accuracy for lower memory and CPU costs. This package does that.
Re: Perks – Effectively compute quantiles for unbounded data streams
#6Hey, this is very close to something I've been needing recently (and in Go, nonetheless).
Is there any way to get a similar thing for a sliding window of a stream? For example, to be able to report (estimated) 90th percentile latencies for server requests in the last 5 minutes, hour, and day.
Re: Perks – Effectively compute quantiles for unbounded data streams
#7Hey, this is very close to something I've been needing recently (and in Go, nonetheless). Is there any way to get a similar thing for a sliding window of a stream? For example, to be able to report (estimated) 90th percentile latencies for server requests in the last 5 minutes, hour, and day.
Yes. I use this for that. Query then Reset every 5 minutes.
Re: Perks – Effectively compute quantiles for unbounded data streams
#8Hey, this is very close to something I've been needing recently (and in Go, nonetheless). Is there any way to get a similar thing for a sliding window of a stream? For example, to be able to report (estimated) 90th percentile latencies for server requests in the last 5 minutes, hour, and day.
Yes. I use this for that. Query then Reset every 5 minutes.
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?)
Re: Perks – Effectively compute quantiles for unbounded data streams
#9Hey, this is very close to something I've been needing recently (and in Go, nonetheless). Is there any way to get a similar thing for a sliding window of a stream? For example, to be able to report (estimated) 90th percentile latencies for server requests in the last 5 minutes, hour, and day.
Yes. I use this for that. Query then Reset every 5 minutes.
[deleted]
Re: Perks – Effectively compute quantiles for unbounded data streams
#10Earlier quoted context omitted.
Yes. I use this for that. Query then Reset every 5 minutes.
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?)
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.