topic: sketch

192 modules sharing the sketch name family (derived from the tree's prefix discipline).

Probabilistic data structures — count-min, HyperLogLog-class cardinality, tuple sketches and friends — implemented and benchmarked as the tree's approximate-counting substrate. The largest single topic by code volume: streaming measurement is a first-class citizen here, which is consistent with the house rule that every claim be a measured number.

narrated overview -- maintained by the narration lane, module links verified against this wiki.

module	description	lines	funcs
nx_sketch_ams.nx	AMS sketch (Alon-Matias-Szegedy 1996).	217	11
nx_sketch_bit_vector.nx	dense bit vector with popcount + bitwise ops.	249	18
nx_sketch_bloom.nx	Bloom filter v2 (sovereign-tier with typed envelope).	168	10
nx_sketch_buglog.nx	5W+H+GLP provenance ledger primitive.	338	34
nx_sketch_cms.nx	Count-Min Sketch in NishiLang.	219	9
nx_sketch_comparator.nx	sealed-verdict comparator for head-to-head stomp claims.	220	7
nx_sketch_correlation.nx	streaming Pearson correlation + linear regression.	211	12
nx_sketch_count_sketch.nx	CountSketch (Charikar-Chen-Farach-Colton 2002).	224	13
nx_sketch_counting_bloom.nx	Counting Bloom filter (Fan-Cao-Almeida-Broder 1998).	253	13
nx_sketch_cpc.nx	CPC sparse-mode cardinality sketch (Lang 2017 / FM85).	196	12
nx_sketch_cpc_dense.nx	CPC dense bitmap mode + HIP estimator.	228	14
nx_sketch_cuckoo.nx	Cuckoo Filter (Fan et al. 2014).	283	18
nx_sketch_cusum.nx	CUSUM change-point detector (Page 1954).	139	11
nx_sketch_ddsketch.nx	DDSketch (Masson et al, PVLDB 2019).	208	10
nx_sketch_entropy.nx	streaming Shannon entropy estimator.	134	8
nx_sketch_epsilon_greedy.nx	Epsilon-Greedy bandit (Sutton-Barto, classic).	230	14
nx_sketch_ewma.nx	exponentially-weighted moving average (EWMA).	137	8
nx_sketch_geomean.nx	streaming geometric mean via log-space accumulation.	147	11
nx_sketch_hash_map.nx	open-addressing hash map (i64 -> i64).	262	17
nx_sketch_histogram.nx	fixed-bin histogram with quantile + merge.	217	14
nx_sketch_hll.nx	HyperLogLog cardinality sketch in NishiLang.	500	13
nx_sketch_hll4.nx	HLL_4 with Heule exception table.	276	12
nx_sketch_hll_packed.nx	4-bit and 6-bit packed-register HLL.	212	7
nx_sketch_hll_provenance.nx	sample CAPABILITY + IMPROVEMENT_OPP entries	87	1
nx_sketch_hll_provenance_v2.nx	post-bias-table provenance entries.	70	1
nx_sketch_hllmap.nx	Map<key, HLL> for "distinct count per key" queries.	251	13
nx_sketch_holt.nx	Holt's linear method (double exponential smoothing).	139	8
nx_sketch_kll.nx	compactor-hierarchy quantile sketch.	317	13
nx_sketch_kmeans1d.nx	streaming 1D k-means clustering.	191	12
nx_sketch_kmv.nx	KMV (K-Minimum-Values) sketch.	316	10
nx_sketch_linear_counter.nx	Linear Counting (Whang-Vander Zanden 1990).	229	13
nx_sketch_lossy_counting.nx	Manku-Motwani 2002 Lossy Counting.	237	14
nx_sketch_mann_kendall.nx	streaming Mann-Kendall trend test.	178	10
nx_sketch_markov.nx	discrete-state Markov chain transition tracker.	204	12
nx_sketch_min_heap.nx	binary min-heap (priority queue) primitive.	202	13
nx_sketch_misra_gries.nx	Misra-Gries frequent items (1982).	231	13
nx_sketch_moments.nx	streaming higher moments (skewness + kurtosis).	222	15
nx_sketch_naive_bayes.nx	streaming binary Naive Bayes classifier.	198	12
nx_sketch_reservoir.nx	Vitter reservoir sampling + quantile.	188	10
nx_sketch_robust_hll.nx	adversarial-safe HLL via median-of-k.	207	7
nx_sketch_segment_tree.nx	segment tree for range sum / min / max queries.	210	12
nx_sketch_sliding_window.nx	last-W-samples rolling aggregator.	187	12
nx_sketch_space_saving.nx	SpaceSaving top-K heavy hitters.	226	12
nx_sketch_stream_stats.nx	streaming mean / variance / stddev / min / max.	213	14
nx_sketch_tdigest.nx	T-Digest (Dunning 2019) tail-tight quantile sketch.	340	11
nx_sketch_theta.nx	Theta sketch (Beyer/Haas 2014).	377	11
nx_sketch_tuple.nx	Tuple sketch (Theta + per-hash auxiliary data).	328	12
nx_sketch_types.nx	L-4 typed envelope scaffold for streaming sketches.	91	1
nx_sketch_types_kat.nx	KAT for nx_sketch_types (ApproxI64 typed-envelope scaffold; 53 children).	45	3
nx_sketch_ucb1.nx	UCB1 multi-armed bandit (Auer-Cesa-Bianchi-Fischer 2002).	235	12
nx_sketch_union_find.nx	Disjoint Set Union (Union-Find) primitive.	158	8
nx_sketch_varopt.nx	Weighted reservoir sampling (Efraimidis-Spirakis 2006 / Cohen 2011).	245	12
nx_sketch_zscore.nx	point z-score anomaly detector.	134	10
sketch_ams.nx	AMS sketch (Alon-Matias-Szegedy 1996).	231	11
sketch_ams_test.nx	AMS F_2 estimator verification.	110	2
sketch_ams_vs_naive_bench.nx	AMS F_2 vs naive exact tracker.	126	2
sketch_bit_vector.nx	dense bit vector with popcount + bitwise ops.	243	18
sketch_bit_vector_test.nx	dense bit vector verification.	117	1
sketch_bloom.nx	Bloom filter v2 (sovereign-tier with typed envelope).	162	10
sketch_bloom_test.nx	Bloom v2 verification.	109	1
sketch_buglog.nx	5W+H+GLP provenance ledger primitive.	331	34
sketch_buglog_test.nx	ID-based G + L referencing docs/{genealogy,lineage}.md.	76	1
sketch_cb_vs_cuckoo_delete_bench.nx	both-support-delete paired bench.	135	2
sketch_cms.nx	Count-Min Sketch in NishiLang.	213	9
sketch_cms_test.nx	Count-Min Sketch behavioral test.	137	2
sketch_comparator.nx	sealed-verdict comparator for head-to-head stomp claims.	211	7
sketch_comparator_test.nx	sealed-verdict comparator validation.	120	1
sketch_correlation.nx	streaming Pearson correlation + linear regression.	205	12
sketch_correlation_test.nx	streaming Pearson + regression verification.	158	2
sketch_count_sketch.nx	CountSketch (Charikar-Chen-Farach-Colton 2002).	230	13
sketch_count_sketch_negative_bench.nx	negative-insert capability bench.	165	3
sketch_count_sketch_test.nx	CountSketch (unbiased frequency) verification.	113	2
sketch_count_sketch_vs_cms_bias_bench.nx	bias-direction paired bench.	187	3
sketch_counting_bloom.nx	Counting Bloom filter (Fan-Cao-Almeida-Broder 1998).	247	13
sketch_counting_bloom_test.nx	Counting Bloom with delete + multi-set.	144	1
sketch_cpc.nx	CPC sparse-mode cardinality sketch (Lang 2017 / FM85).	188	12
sketch_cpc_dense.nx	CPC dense bitmap mode + HIP estimator.	219	14
sketch_cpc_dense_test.nx	CPC dense-mode verification.	137	2
sketch_cpc_test.nx	CPC (sparse + HIP estimator) verification.	140	2
sketch_cuckoo.nx	Cuckoo Filter (Fan et al. 2014).	277	18
sketch_cuckoo_delete_vs_bloom_bench.nx	DELETE capability bench.	151	2
sketch_cuckoo_test.nx	Cuckoo Filter end-to-end verification.	136	1
sketch_cusum.nx	CUSUM change-point detector (Page 1954).	133	11
sketch_cusum_test.nx	CUSUM change-point detector verification.	121	1
sketch_cusum_vs_threshold_bench.nx	change-point detection bench.	99	1
sketch_ddsketch.nx	DDSketch (Masson et al, PVLDB 2019).	264	10
sketch_ddsketch_test.nx	DDSketch multiplicative-error quantile verification.	147	2
sketch_ddsketch_vs_tdigest_tail_bench.nx	multiplicative-error tail.	128	2
sketch_entropy.nx	streaming Shannon entropy estimator.	128	8
sketch_entropy_test.nx	streaming Shannon entropy verification.	123	2
sketch_epsilon_greedy.nx	Epsilon-Greedy bandit (Sutton-Barto, classic).	224	14
sketch_epsilon_greedy_test.nx	epsilon-greedy bandit verification.	152	3
sketch_ewma.nx	exponentially-weighted moving average (EWMA).	131	8
sketch_ewma_test.nx	EWMA streaming smoother verification.	97	2
sketch_freq_directions.nx	Liberty 2013 Frequent Directions sketch.	477	25
sketch_freq_directions_test.nx	FD verification.	125	2
sketch_freq_directions_vs_topnorm_bench.nx	paired bench, FD vs naive top-norm.	223	4
sketch_geomean.nx	streaming geometric mean via log-space accumulation.	141	11
sketch_geomean_test.nx	geometric mean via log-space accumulation tests.	93	2
sketch_hash_map.nx	open-addressing hash map (i64 -> i64).	256	17
sketch_hash_map_test.nx	hash map foundational primitive verification.	135	1
sketch_histogram.nx	fixed-bin histogram with quantile + merge.	211	14
sketch_histogram_test.nx	fixed-bin histogram + quantile + merge.	145	2
sketch_hll.nx	HyperLogLog cardinality sketch in NishiLang.	563	15
sketch_hll4.nx	HLL_4 with Heule exception table.	270	12
sketch_hll4_test.nx	HLL_4 + Heule exception table verification.	111	2
sketch_hll4_vs_hll8_bench.nx	memory-efficiency paired bench.	103	3
sketch_hll_lgk12_vs_lgk8_bench.nx	validates bits-up cap raise.	112	3
sketch_hll_packed.nx	4-bit and 6-bit packed-register HLL.	206	7
sketch_hll_packed_test.nx	end-to-end test for HLL_6 packed	92	2
sketch_hll_packed_vs_hll8_bench.nx	6-bit register memory bench.	89	3
sketch_hll_provenance.nx	sample CAPABILITY + IMPROVEMENT_OPP entries	81	1
sketch_hll_provenance_v2.nx	post-bias-table provenance entries.	64	1
sketch_hll_test.nx	end-to-end test for the NishiLang HLL port.	96	3
sketch_hll_vs_materialized_set_bench.nx	STRUCTURAL class comparison.	117	3
sketch_hllmap.nx	Map<key, HLL> for "distinct count per key" queries.	245	13
sketch_hllmap_merge_capability_bench.nx	capability-EXCEED bench.	200	3
sketch_hllmap_test.nx	HllMap (distinct-per-key) with merge.	170	2
sketch_holt.nx	Holt's linear method (double exponential smoothing).	133	8
sketch_holt_test.nx	Holt's linear forecast verification.	86	2
sketch_holt_vs_ewma_trended_bench.nx	trend tracking paired bench.	79	2
sketch_kll.nx	compactor-hierarchy quantile sketch.	325	13
sketch_kll_test.nx	KLL/MRL compactor-cascade verification.	110	2
sketch_kll_vs_reservoir_bench.nx	MATCHED-MEMORY honest measurement.	140	2
sketch_kmeans1d.nx	streaming 1D k-means clustering.	185	12
sketch_kmeans1d_test.nx	1D streaming k-means verification.	104	2
sketch_kmv.nx	KMV (K-Minimum-Values) sketch.	310	10
sketch_kmv_jaccard_vs_naive_bench.nx	KMV Jaccard vs naive O(N).	156	3
sketch_kmv_test.nx	KMV cardinality + union + Jaccard verification.	196	2
sketch_lc_vs_hll_small_n_bench.nx	LC sweet-spot paired bench.	90	3
sketch_linear_counter.nx	Linear Counting (Whang-Vander Zanden 1990).	223	13
sketch_linear_counter_test.nx	Whang-Vander Zanden 1990 cardinality.	158	2
sketch_lossy_counting.nx	Manku-Motwani 2002 Lossy Counting.	231	14
sketch_lossy_counting_test.nx	Manku-Motwani Lossy Counting verification.	99	1
sketch_mann_kendall.nx	streaming Mann-Kendall trend test.	172	10
sketch_mann_kendall_test.nx	streaming Mann-Kendall trend test verification.	100	1
sketch_mann_kendall_vs_endpoint_bench.nx	trend detection bench.	90	1
sketch_markov.nx	discrete-state Markov chain transition tracker.	198	12
sketch_markov_test.nx	Markov chain transition tracker verification.	126	2
sketch_markov_vs_uniform_bench.nx	transition prediction bench.	91	2
sketch_mg_ss_bracket_bench.nx	bracketing capability paired bench.	166	1
sketch_min_heap.nx	binary min-heap (priority queue) primitive.	196	13
sketch_min_heap_test.nx	binary min-heap verification.	123	1
sketch_misra_gries.nx	Misra-Gries frequent items (1982).	225	13
sketch_misra_gries_test.nx	MG heavy hitters (under-estimate variant).	116	2
sketch_moments.nx	streaming higher moments (skewness + kurtosis).	216	15
sketch_moments_test.nx	streaming skewness + kurtosis verification.	124	2
sketch_naive_bayes.nx	streaming binary Naive Bayes classifier.	192	12
sketch_naive_bayes_test.nx	binary Naive Bayes classifier verification.	85	1
sketch_naive_bayes_vs_majority_bench.nx	classification accuracy bench.	127	1
sketch_observability_dashboard_bench.nx	COMPOSITION integration bench.	192	3
sketch_reqsketch.nx	relative-error streaming quantile sketch.	380	14
sketch_reqsketch_test.nx	ReqSketch verification.	134	2
sketch_reqsketch_vs_kll_bench.nx	MATCHED-MEMORY paired measurement.	134	2
sketch_reservoir.nx	Vitter reservoir sampling + quantile.	182	10
sketch_reservoir_test.nx	Vitter reservoir + sample-based	131	2
sketch_robust_hll.nx	adversarial-safe HLL via median-of-k.	203	7
sketch_robust_hll_test.nx	adversarial-safety smoke for the	95	3
sketch_robust_hll_vs_hll_adv_bench.nx	adversarial paired bench.	133	3
sketch_segment_tree.nx	segment tree for range sum / min / max queries.	204	12
sketch_segment_tree_test.nx	range sum / min / max verification.	133	1
sketch_sliding_window.nx	last-W-samples rolling aggregator.	181	12
sketch_sliding_window_test.nx	last-W-samples rolling aggregator tests.	86	1
sketch_space_saving.nx	SpaceSaving top-K heavy hitters.	220	12
sketch_space_saving_test.nx	SpaceSaving behavioral test.	120	1
sketch_stream_stats.nx	streaming mean / variance / stddev / min / max.	207	14
sketch_stream_stats_test.nx	streaming mean / variance / stddev / merge.	127	2
sketch_tdigest.nx	T-Digest (Dunning 2019) tail-tight quantile sketch.	340	11
sketch_tdigest_test.nx	T-Digest quantile + tail-tight verification.	96	2
sketch_tdigest_v2.nx	T-Digest with Dunning k1 arcsin-based scale.	359	14
sketch_tdigest_v2_test.nx	V2 (Dunning k1 arcsin scale) verification.	123	2
sketch_tdigest_v2_vs_v1_bench.nx	paired measurement, T-Digest v2 vs v1.	113	1
sketch_tdigest_vs_materialized_quantile_bench.nx	streaming quantile EXCEED.	86	2
sketch_theta.nx	Theta sketch (Beyer/Haas 2014).	371	11
sketch_theta_intersect_vs_hll_bench.nx	capability bench, Theta vs HLL.	143	3
sketch_theta_test.nx	Theta sketch union + intersection + difference.	143	2
sketch_thompson.nx	Thompson Sampling (Bernoulli-Beta bandit).	292	16
sketch_thompson_test.nx	Thompson Sampling verification.	140	2
sketch_thompson_vs_ucb1_bench.nx	paired measurement, Thompson vs UCB1.	118	1
sketch_tuple.nx	Tuple sketch (Theta + per-hash auxiliary data).	322	12
sketch_tuple_test.nx	Tuple sketch (Theta + scalar) with reducer + merge.	166	2
sketch_types.nx	L-4 typed envelope scaffold for streaming sketches.	86	1
sketch_types_gate.nx	the gate for the typed loss-envelope 139 modules import.	93	1
sketch_ucb1.nx	UCB1 multi-armed bandit (Auer-Cesa-Bianchi-Fischer 2002).	229	12
sketch_ucb1_test.nx	multi-armed bandit verification.	123	3
sketch_union_find.nx	Disjoint Set Union (Union-Find) primitive.	152	8
sketch_union_find_test.nx	Disjoint Set Union verification.	134	1
sketch_varopt.nx	Weighted reservoir sampling (Efraimidis-Spirakis 2006 / Cohen 2011).	239	12
sketch_varopt_test.nx	Weighted reservoir sampling verification.	111	1
sketch_varopt_vs_reservoir_biased_bench.nx	weighted sampling capability.	111	1
sketch_zscore.nx	point z-score anomaly detector.	128	10
sketch_zscore_test.nx	z-score anomaly detector verification.	104	2