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?
 A: 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
A: 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.
