nx_sketch_cms.nx

sketch_cms.nx -- Count-Min Sketch in NishiLang. Cormode-Muthukrishnan 2005. d-row x w-column counter grid; add() increments d counters chosen by d hash functions of the item; estimate() returns the MIN across rows -- overestimate- only by construction (no false negatives). Provable bound: Pr[estimate(x) <= true(x) + eps * totalCount] >= 1 - delta for d = ceil(ln(1/delta)), w = ceil(e / eps) Defaults d=5, w=2718 -> eps ~ 0.001, delta ~ 0.007 (~ e^-5). Memory: 8 * d * w bytes (i64 counters). d=5, w=2718 -> 109 KB. KIRSCH-MITZENMACHER 2008 double-hashing: Instead of d independent murmur calls, compute ONE 64-bit hash (hi, lo) and derive d row indices via h_i(x) = (hi + i * lo) ^ seeds[i] mod w. Gives near-independent rows at single-hash cost. Mirrors core-sketch/cms.ts. LOSSLESS-LANGUAGE DISCIPLINE (doc 20): nx_cms_query returns ApproxI64 with envelope_kind = NX_ENV_ABS (absolute additive bound = eps * totalCount), NOT rel_stddev. Substrate's typed envelope discriminator forces callers to handle the abs-vs-relative distinction explicitly.