I'm looking for a simple data structure that will let me compute arbitrary approximate quantiles, within a percent or two error, on a stream of 64-bit integers (think of $n$ as being potentially as high as a trillion or so).

In order of importance, it would have the following desired traits:

1) Fast update time, at most a few hundred cycles per element in the stream, but even lower is better

2) Memory usage of at most a few hundred bytes per stream

3) Simplicity of implementation. Hopefully no more than a few hours to implement. Properties 1 and 2 are essential, but this one is also very important as well.

I encountered the following paper, which suggests that Q-Digest may be a good option. Is this true, and are there any other possibilities I should be aware of?

  • $\begingroup$ QDigest is still the best for quantile estimation. If you're interested in finding frequent items instead (a slightly different problem), then there are other approaches. $\endgroup$ May 10 '11 at 3:17
  • $\begingroup$ its space usage is not asymptotically optimal for inserts only, but CM sketches are hard to beat when it comes to simplicity. $\endgroup$ May 10 '11 at 5:46
  • $\begingroup$ @SashoNikolov: I'm sure your advisor will be happy to hear that ;) $\endgroup$ May 10 '11 at 8:53
  • $\begingroup$ @Suresh: I've made a vow to promote CM sketches :) $\endgroup$ May 10 '11 at 15:19

Your Answer

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

Browse other questions tagged or ask your own question.