<p>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).</p>

<p>In order of importance, it would have the following desired traits:</p>

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

<p>2) Memory usage of at most a few hundred bytes per stream</p>

<p>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.</p>

<p>I encountered the following <a href="http://www.cs.ucsb.edu/~suri/psdir/ency.pdf" rel="nofollow">paper</a>, which suggests that Q-Digest may be a good option. Is this true, and are there any other possibilities I should be aware of?</p>

CC BY-SA 3.0
2011-05-10T03:17:05.487Z
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
CC BY-SA 3.0
2011-05-10T05:46:00.380Z
its space usage is not asymptotically optimal for inserts only, but CM sketches are hard to beat when it comes to simplicity.
Sasho Nikolov
CC BY-SA 3.0
2011-05-10T08:53:09.773Z
@SashoNikolov: I'm sure your advisor will be happy to hear that ;)
Suresh Venkat
CC BY-SA 3.0
2011-05-10T15:19:41.393Z
@Suresh: I've made a vow to promote CM sketches :)
Sasho Nikolov
<ds.algorithms><ds.data-structures><data-streams>
Simple to implement approximate quantile data structure for a stream of integers?
jonderry
# Simple to implement approximate quantile data structure for a stream of integers?

(Asked by: username_0 on 2011-05-10)

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](http://www.cs.ucsb.edu/~suri/psdir/ency.pdf), which suggests that Q-Digest may be a good option. Is this true, and are there any other possibilities I should be aware of?

**Tags:** ds.algorithms, ds.data-structures, data-streams
> **Comments:**
> **username_1**: 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.  
> **username_2**: its space usage is not asymptotically optimal for inserts only, but CM sketches are hard to beat when it comes to simplicity.  
> **username_1**: @SashoNikolov: I'm sure your advisor will be happy to hear that ;)  
> **username_2**: @Suresh: I've made a vow to promote CM sketches :)  

---

## 0 answers

