sketch_count_sketch_vs_cms_bias_bench.nx
buildroot/runtime/sketch_count_sketch_vs_cms_bias_bench.nx
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
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
structs
| none |
consts
| none |
functions
| 36 | func iabs_b(x: i64) -> i64 called by 1: main |
| 41 | func write_b(buf: *u8, value: i64) -> i64 called by 1: main |
| 52 | func main() -> i64 |