21
$\begingroup$

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?

|cite|improve this question|||||
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – cardinal May 9 '11 at 12:23
  • $\begingroup$ 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. $\endgroup$ – jonderry May 9 '11 at 16:14
  • $\begingroup$ Did you see this question? $\endgroup$ – cardinal May 10 '11 at 12:20
15
$\begingroup$

You don't state this explicitly, but from your description of the problem it seems likely that you're after a high-biased set of quantiles (e.g., 50th, 90th, 95th and 99th percentiles).

If that's the case, I've had a lot of success with the method described in "Effective Computation of Biased Quantiles over Data Streams" by Cormode et al. It's a fast algorithm that requires little memory and that's easy to implement.

The method is based on an earlier algorithm by Greenwald and Khanna that maintains a small sample of the input stream along with upper and lower bounds on the rank of the values in the sample. It requires more space than a collection of few moments, but will be much better at describing the interesting tail region of the distribution accurately.

|cite|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Suresh Venkatasubramanian May 12 '11 at 22:33
3
$\begingroup$

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.

See https://github.com/tdunning/t-digest

|cite|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.