# Simple to implement approximate quantile data structure for a stream of integers?

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?

• 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. – Suresh Venkat May 10 '11 at 3:17
• its space usage is not asymptotically optimal for inserts only, but CM sketches are hard to beat when it comes to simplicity. – Sasho Nikolov May 10 '11 at 5:46
• @SashoNikolov: I'm sure your advisor will be happy to hear that ;) – Suresh Venkat May 10 '11 at 8:53
• @Suresh: I've made a vow to promote CM sketches :) – Sasho Nikolov May 10 '11 at 15:19