sketch_ams_vs_naive_bench.nx
buildroot/runtime/sketch_ams_vs_naive_bench.nx
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
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
structs
| none |
consts
| none |
functions
| 30 | func iabs_am(x: i64) -> i64 called by 1: main |
| 35 | func main() -> i64 |