sketch_ams.nx

sketch_ams.nx -- AMS sketch (Alon-Matias-Szegedy 1996). Estimates F_2 = Σ f_i² (second frequency moment) of a stream over implicit-keyed items. Used for: - self-join size estimation in databases - query-plan cardinality estimation - skew detection (high F_2 = skewed distribution) - L2 norm of frequency vector ALGORITHM: For each of d * s estimators, a random ±1 sign function ξ_jk. On (item x, count c): counter[j][k] += ξ_jk(x) * c for all (j,k). F_2 estimate per estimator: counter[j][k]² Within-group AVERAGE: F_2_j = mean of counter[j][k]² over k. Across-group MEDIAN: F_2 ≈ median(F_2_j) across j. Variance: average reduces variance by 1/s. Median over d independent estimates boosts confidence to 1 - 2^(-d/2). MEMORY: d * s * 8 bytes. d=5, s=64 -> 2560 bytes for F_2 with 12.5% relative error at 87.5% confidence. LOSSLESS-LANGUAGE DISCIPLINE: nx_ams_query returns ApproxI64 with NX_ENV_REL_STDDEV = 1/sqrt(s) per estimator (further tightened by median-of-d boost in practice). conf_ppb tracks (1 - 2^(-d/2)).