DataSketches.Quantiles.RelativeErrorQuantile

Relative Error Quantiles (REQ) sketch for approximate quantile computation with relative error bounds.

Most quantile sketches (like KLL) have additive error: the answer might be off by, say, 1.3% of the full rank range no matter where you query. That's fine for p50 or p90, but at p99.99 a 1.3% additive error is enormous relative to the sliver of the distribution you're looking at.

REQ flips this: the error is /proportional to the distance from the nearest tail/. At p99.99, the error is proportional to 0.01%, not 1.3%. This makes REQ the right choice when you care specifically about extreme percentiles — SLA monitoring at p99.9, tail-latency debugging, outlier detection.

For general-purpose quantiles where you don't need tail precision, prefer DataSketches.Quantiles.KLL — it's faster and simpler.

Based on "Relative Error Streaming Quantiles" (Cormode et al., PODS 2021).

Configuration

k controls accuracy vs. space. Must be even, in [4, 1024]. Larger k means tighter error bounds but more memory. k = 12 is a reasonable default.

RankAccuracy selects which tail gets the better error guarantee:

• HighRanksAreAccurate — use when you care about p99, p99.9, p99.99

• LowRanksAreAccurate — use when you care about p1, p0.1, p0.01

Usage

import qualified DataSketches.Quantiles.RelativeErrorQuantile as REQ

main :: IO ()
main = do
  sk <- REQ.mkReqSketch 12 REQ.HighRanksAreAccurate
  mapM_ (REQ.insert sk) [1..100000 :: Double]
  p999 <- REQ.quantile sk 0.999
  putStrLn $ "p99.9 = " ++ show p999

Implementation

Backed by a C implementation (cbits/req.c) behind a ForeignPtr. All sketch memory lives outside the GHC heap — zero GC pressure, zero boxing overhead.

Mergeability

REQ sketches are fully mergeable: two sketches built on separate data partitions can be combined via merge to produce a sketch equivalent to having processed all data in a single stream. Both sketches must share the same RankAccuracy setting.