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 better2) Memory usage of at most a few hundred bytes per stream3) 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?
Simple to implement approximate quantile data structure for a stream of integers?
ds.algorithms;ds.data structures;data streams