sketch_reqsketch.nx

sketch_reqsketch.nx -- relative-error streaming quantile sketch. Cormode-Karnin-Liberty-Thaler-Vesely 2021, "Relative Error Streaming Quantiles" (FOCS / VLDB). ReqSketch tightens KLL on tail queries: where KLL bounds |rank_est - rank_true| <= eps * N (additive in N), ReqSketch bounds |rank_est - rank_true| <= eps * min(rank_true, N - rank_true) (multiplicative in the rank's distance from the nearer extreme). Tail quantiles (p99 / p99.9 / p0.1) get strictly tighter guarantees as N grows. COMPLEMENTS KLL + T-DIGEST: - KLL: provable uniform additive bound; loose at tails. - T-Digest: empirically tail-tight; no global rank guarantee. - ReqSketch: provable multiplicative tail bound; strictly stronger than KLL for tail queries at large N. CONSTRUCTION (simplified reference impl, hra = "high-rank- accurate" upper-tail-tight variant -- mirror with hra=0 for lower-tail-tight): Compactor cascade like KLL, but the compact() rule preserves the upper section of each compactor exactly (no down-sampling) while KLL-coin-flipping the lower section. Section size shrinks linearly with level -- at level h, preserve_count_h = max(1, k - 2*h), so at high levels almost all items get evicted, while at low levels half stay in place. Items preserved at level h carry weight 2^h same as KLL; coin-flipped survivors get weight 2^(h+1) upon promotion. SIMPLIFICATION VS PAPER (honest scope): Paper uses numSections in {3, 6, 12, ...} growing geometrically with N and section_size = sqrt(2) * k_base * 2^(-h/2). We use numSections=2 fixed and section_size = max(1, k/2 - h) linear shrinkage. Same asymptotic shape (eps ~ 1/sqrt(k)), slightly looser constant. v2 will swap in the geometric schedule. LOSSLESS-LANGUAGE DISCIPLINE (doc 20): Query returns ApproxI64 with envelope_kind = NX_ENV_REL_RANK_ERROR, param_a = eps_ppb (relative rank error * 1e9), conf = 0.95, maturity = ReferenceImpl, adv = Honest.