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 14 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)

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

main nx_cs_alloc nx_cms_alloc nx_cs_add nx_cs_h1 nx_cs_h2 nx_cs_sign write_b nx_cms_add murmur3_32 mm_load_u32_le mm_rotl32 nx_cms_row_index nx_cs_estimate nx_cs_h1 ↻ nx_cs_h2 ↻ nx_cs_sign ↻ nx_cms_estimate murmur3_32 ↻ nx_cms_row_index ↻ nx_cmp_accuracy nx_cmp_iabs iabs_b nx_cmp_memory

structs

none

consts

none

functions

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