  We present on-line algorithms for computing approximations of rank-based
statistics that give high accuracy, particularly near the tails of a
distribution, with very small sketches. Notably, the method allows a quantile
$q$ to be computed with an accuracy relative to $\max(q, 1-q)$ rather than
absolute accuracy as with most other methods. This new algorithm is robust with
respect to skewed distributions or ordered datasets and allows separately
computed summaries to be combined with no loss in accuracy.
  An open-source Java implementation of this algorithm is available from the
author. Independent implementations in Go and Python are also available.
