Compute approximate quantiles for a stream of integers using moments?

migrated from math.stackexchange.

I'm processing a long stream of integers and am considering tracking a few moments in order to be able to approximately compute various percentiles for the stream without storing much data. What's the simplest way to compute percentiles from a few moments. Is there a better approach that involves only storing a small amount of data?

• Do you know anything specific about the distributional properties of your stream? For example, are they, say, positive? Bounded? Any other details you can provide will be helpful. Moments are pretty easy to calculate and store for a stream. There are also previous questions here about directly estimating quantiles from a stream, which sounds like what you really are trying to do. You might search for, and look through, those. Commented May 9, 2011 at 12:23
• They represent processing times, so they are positive, and mostly tightly clustered unless there is some sort of technical problem or overload in the system. I'll look for the quantile questions; they might be good enough. Still I'm curious how to go from moments to computing the value associated with an arbitrary percentile. I know storing moments is easy, it's how to use them that I don't know. Commented May 9, 2011 at 16:14
• Did you see this question? Commented May 10, 2011 at 12:20

• Yes, this is indeed the way to go. in fact it's a little easier to get estimates of the high quantiles, especially if you're willing to tolerate error in the rank of the form $\epsilon n$ where $n$ is the total number of items, and \epsilon > 0$is some user defined error term Commented May 12, 2011 at 22:33 There is a more recent and much simpler algorithm for this that provides very good estimates of the extreme quantiles. The basic idea is that smaller bins are used at the extremes in a way that both bounds the size of the data structure and guarantees higher accuracy for small or large$q\$. The algorithm is available in several languages and many packages. The MergingDigest version requires no dynamic allocation ... once the MergingDigest is instantiated, no further heap allocation is required.