code wiki / (root) / nx_sketch_kll.nx

nx_sketch_kll.nx

buildroot/runtime/nx_sketch_kll.nx

10292 B317 linesdepth 3pulls 3 transitivereach 0 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_kll.nx -- compactor-hierarchy quantile sketch. MRL99-style (Manku-Rajagopalan-Lindsay 1999) "compactor cascade": maintain levels 0, 1, 2, ... each holding up to k items. Items at level h carry weight 2^h. When level h fills, sort it, flip a coin, promote either even-indexed or odd-indexed items to level h+1 (the other half discarded). Karnin-Lang-Liberty 2016 (FOCS) tightens this via geometric per-level capacity decay; we use uniform capacity here for simpler code at slightly looser bound. Rank-error declared conservatively as ~1/sqrt(k) at conf 0.95. Versus Reservoir (sketch_reservoir.nx): KLL/MRL has tighter rank-error at fixed memory because the weighted-promotion cascade preserves rank information that uniform reservoir sampling discards. At k=200, MRL eps ~ 0.07 vs Reservoir eps ~ 0.085 (similar but slightly tighter); the win compounds at higher k. LOSSLESS-LANGUAGE DISCIPLINE (doc 20): Same NX_ENV_RANK_ERROR envelope as Reservoir; substrate doesn't double-count. Multiple primitives sharing an envelope kind is fine -- the discriminator is about the SHAPE of the error, not uniqueness.

dependencies 2 imports · 0 importers

nx_syscalls.nx nx_sketch_types.nx nx_sketch_kll.nx

imports: nx_syscalls.nxnx_sketch_types.nx

imported by: nobody (leaf or entry point)

structs

45struct Kll

consts

36const NX_KLL_K_MIN: i64 = 8
37const NX_KLL_K_MAX: i64 = 10000
38const NX_KLL_MAX_LEVELS: i64 = 16
41const NX_KLL_LCG_A: i64 = 1103515245
42const NX_KLL_LCG_C: i64 = 12345
43const NX_KLL_LCG_MOD: i64 = 0x7FFFFFFF

functions

58func nx_kll_alloc(k: i64, seed: i64) -> *Kll
calls 1: sys_mmap
84func nx_kll_rng_next(s: *Kll) -> i64
called by 1: nx_kll_compact
93func nx_kll_level_addr(s: *Kll, level: i64) -> *i64
97func nx_kll_sort_level(s: *Kll, level: i64) -> i64
called by 1: nx_kll_compact calls 1: nx_kll_level_addr
124func nx_kll_compact(s: *Kll, level: i64) -> i64
165func nx_kll_add(s: *Kll, value: i64) -> i64
181func nx_kll_total_weight(s: *Kll) -> i64
198func nx_kll_quantile(s: *Kll, p_milli: i64) -> i64
260func nx_kll_rank(s: *Kll, value: i64) -> i64
291func nx_kll_rank_error_ppb(k: i64) -> i64
300func nx_kll_query_quantile(s: *Kll, p_milli: i64) -> *ApproxI64
311func nx_kll_memory_bytes(s: *Kll) -> i64
315func nx_kll_levels_used(s: *Kll) -> i64