code wiki / (root) / sketch_count_sketch_vs_cms_bias_bench.nx

sketch_count_sketch_vs_cms_bias_bench.nx

buildroot/runtime/sketch_count_sketch_vs_cms_bias_bench.nx

5895 B187 linesdepth 7pulls 16 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_count_sketch_vs_cms_bias_bench.nx -- bias-direction paired bench. CLAIM TO VALIDATE: CountSketch (Charikar-Chen-Farach-Colton 2002) is UNBIASED: its per-row sign hash h2 means expected error = 0, errors are two-sided. Count-Min Sketch (Cormode-Muthukrishnan 2005) is one-sided BIASED: estimates are always >= true (min over d rows, all rows >= truth by collision additivity). DataSketches ships ONLY CMS in the frequency family; CountSketch is queued. Substrate ships both; this bench demonstrates the error-direction win on a representative Zipfian stream. WORKLOAD: 5 heavy items + 5000 noise singletons. Total stream ~8800 inserts. Both sketches: d=5, w=256. MEASUREMENT: For each heavy item, compute: cms_bias = cms_est - true cs_bias = cs_est - true Headline CAPABILITY EXCEED: cms_bias >= 0 for ALL heavy items (one-sided), cs_bias may be negative for some (two-sided). Headline ACCURACY EXCEED: |cs_bias| <= |cms_bias| for heaviest items where additive noise dominates -- CountSketch's signed cancellation tightens the estimate.

dependencies 5 imports · 0 importers

syscalls.nx sketch_count_sketch.nx sketch_cms.nx sketch_comparator.nx sketch_types.nx sketch_count_sketch_vs_cms_bia

imports: syscalls.nxsketch_count_sketch.nxsketch_cms.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

structs

none

consts

none

functions

36func iabs_b(x: i64) -> i64
41func write_b(buf: *u8, value: i64) -> i64
52func main() -> i64