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?