nx_sketch_kll.nx
buildroot/runtime/nx_sketch_kll.nx
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
imports: nx_syscalls.nxnx_sketch_types.nx
imported by: nobody (leaf or entry point)
structs
| 45 | struct Kll |
consts
| 36 | const NX_KLL_K_MIN: i64 = 8 |
| 37 | const NX_KLL_K_MAX: i64 = 10000 |
| 38 | const NX_KLL_MAX_LEVELS: i64 = 16 |
| 41 | const NX_KLL_LCG_A: i64 = 1103515245 |
| 42 | const NX_KLL_LCG_C: i64 = 12345 |
| 43 | const NX_KLL_LCG_MOD: i64 = 0x7FFFFFFF |
functions
| 58 | func nx_kll_alloc(k: i64, seed: i64) -> *Kll calls 1: sys_mmap |
| 84 | func nx_kll_rng_next(s: *Kll) -> i64 called by 1: nx_kll_compact |
| 93 | func nx_kll_level_addr(s: *Kll, level: i64) -> *i64 |
| 97 | func nx_kll_sort_level(s: *Kll, level: i64) -> i64 |
| 124 | func nx_kll_compact(s: *Kll, level: i64) -> i64 called by 2: nx_kll_compactnx_kll_add calls 4: nx_kll_sort_levelnx_kll_level_addrnx_kll_rng_nextnx_kll_compact |
| 165 | func nx_kll_add(s: *Kll, value: i64) -> i64 |
| 181 | func nx_kll_total_weight(s: *Kll) -> i64 |
| 198 | func nx_kll_quantile(s: *Kll, p_milli: i64) -> i64 |
| 260 | func nx_kll_rank(s: *Kll, value: i64) -> i64 |
| 291 | func nx_kll_rank_error_ppb(k: i64) -> i64 called by 1: nx_kll_query_quantile |
| 300 | func nx_kll_query_quantile(s: *Kll, p_milli: i64) -> *ApproxI64 |
| 311 | func nx_kll_memory_bytes(s: *Kll) -> i64 |
| 315 | func nx_kll_levels_used(s: *Kll) -> i64 |