Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to estimate the quantile of some data. The data are so huge that they can not be accommodated in the memory. And data are not static, new data keep coming. Does anyone know any algorithm to monitor the quantile(s) of the data observed so far with very limited memory and computation? I find P2 algorithm useful. But it does not work very well for my data, which are extremely heavy-tailed distributed.

share|cite|improve this question
Crossposted:… – cardinal Mar 8 '11 at 5:25

The state of the art in this area has advanced some ways since the mid-1980s. The keywords you should be using in your search are "stream" and "online", both terms used to denote the situation when the size of the input data set (or stream) is far too large to store in memory.

Specifically, I would suggest starting with "Space-Efficient Online Computation of Quantile Summaries" by Greenwald & Khanna and "How to Summarize the Universe" by Gilbert, et. al.

share|cite|improve this answer
Correct. Seems "Sketch" is one of the latest work. – sinoTrinity Mar 9 '11 at 4:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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