sketch_ddsketch.nx

sketch_ddsketch.nx -- DDSketch (Masson et al, PVLDB 2019). Multiplicative-error quantile sketch. Different error model than KLL (additive rank) and T-Digest (scale-function tail-tight): For query rank q, returned value v satisfies: true_value(q) ∈ [v · (1-α), v · (1+α)] I.e., the returned VALUE is within α-relative-error of the true. Perfect for log-distributed metrics (latency, sizes, durations). CAPABILITY: heavy-tail observability. Latency p99=100ms vs p99=1000ms both reported with ±1% multiplicative error, regardless of magnitude. ALGORITHM: bucket(x) = ⌈log_γ(x)⌉ where γ = (1+α)/(1-α) For our integer implementation: octave = bitlen(x) - 1 (floor log2) mantissa = x - (1 << octave) sub_bucket = mantissa * BPO / (1 << octave) bucket_index = octave * BPO + sub_bucket BPO = buckets-per-octave; relative error ≈ 1/BPO. BPO=64 -> ~1.5% multiplicative error BPO=128 -> ~0.8% MEMORY: 64 * BPO * 8 bytes (~32KB for BPO=64, 64KB for BPO=128). MERGE: count-wise addition; matching BPO required. LOSSLESS-LANGUAGE DISCIPLINE: nx_dd_query_quantile returns NX_ENV_REL_STDDEV with param_a = 1/BPO in PPB. Conf = 1e9 (deterministic). MaturityClass = ReferenceImpl.