code wiki / (root) / sketch_ams_vs_naive_bench.nx

sketch_ams_vs_naive_bench.nx

buildroot/runtime/sketch_ams_vs_naive_bench.nx

4094 B126 linesdepth 5pulls 6 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_ams_vs_naive_bench.nx -- AMS F_2 vs naive exact tracker. CLAIM TO VALIDATE: AMS sketch (Alon-Matias-Szegedy 1996) estimates F_2 = sum_i f_i^2 in O(d*s) memory regardless of distinct-item count. Naive exact tracker needs O(distinct_items) memory. Apache DataSketches does NOT ship AMS or any F_2 estimator -- this is greenfield in the summarization-sketch family. WORKLOAD: 1000 distinct items with Zipfian-ish counts. MEASUREMENT AXES: ACCURACY: AMS estimate vs true F_2 (computed naively) AMS bound: rel stddev ~ sqrt(2/s) at conf 0.68. For s=256, rel stddev ~ 0.088, so |AMS - truth|/truth should be <= 2*sigma = 0.176 (95% conf). We allow 25%. MEMORY: AMS bytes vs naive bytes; expect AMS smaller for >100 distinct items. HARD-WIN GATE: MEMORY BEATS by >50% AND AMS estimate within ENV envelope band of truth.

dependencies 4 imports · 0 importers

syscalls.nx sketch_ams.nx sketch_comparator.nx sketch_types.nx sketch_ams_vs_naive_bench.nx

imports: syscalls.nxsketch_ams.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main nx_ams_alloc nx_ams_add nx_ams_f2 nx_ams_cell_idx iabs_am nx_cmp_memory nx_ams_query_f2 nx_ams_f2 ↻ nx_approx_new nx_ams_stderr_ppb nx_ams_isqrt nx_ams_conf_ppb

structs

none

consts

none

functions

30func iabs_am(x: i64) -> i64
called by 1: main
35func main() -> i64