nx_sketch_count_sketch.nx source
↩ module page · 210 lines · 7208 B
1// sketch_count_sketch.nx -- CountSketch (Charikar-Chen-Farach-Colton 2002).
2//
3// Frequency-counting variant that gives UNBIASED estimates via ±1
4// sign hashing. Each (key, count) update adds s_j(key) * count to
5// row j column h_j(key), where s_j ∈ {-1, +1} is a sign hash.
6// Query: median of (s_j(key) * counter[j][h_j(key)]) across rows.
7//
8// COMPLEMENTS CMS (runtime/sketch_cms.nx):
9// - CMS: always OVERESTIMATES (false positives via positive collisions).
10// Use when "upper bound" matters.
11// - CountSketch: UNBIASED. Use when expectation matters (statistical
12// summaries, F_2 estimation, sparse-approximation literature).
13//
14// CAPABILITY STOMP: shipping both means callers pick by error semantics.
15// DataSketches ships CMS as "FrequentLongs"; CountSketch is queued in
16// their docs but not implemented.
17//
18// ERROR BOUND:
19// |estimate(x) - f(x)| <= ε · ||f||_2 / sqrt(d)
20// where ||f||_2 = sqrt(Σ f_i²) is the L2 norm of the frequency vector.
21// For w = O(1/ε²) and d = O(log(1/δ)) rows: confidence 1-δ.
22//
23// Default params: d=5 rows, w=2048 columns -> conf >99%, ε ~ 0.022.
24
25// nx_safety_envelope:
26// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
27// sil_target: SIL1
28// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
29// verdict: NOT_YET_EVALUATED
30
31import "nx_syscalls.nx"
32import "nx_sketch_types.nx"
33import "nx_vecmath.nx"
34
35const NX_CS_MIN_D: i64 = 3
36const NX_CS_MAX_D: i64 = 32
37const NX_CS_MIN_W: i64 = 64
38const NX_CS_MAX_W: i64 = 65536
39
40struct CountSketch {
41 counters: *i64, // d * w grid, in i64 (signed)
42 d: i64,
43 w: i64,
44 seed: i64,
45 total: i64,
46}
47
48// === construction =================================================
49
50func nx_cs_alloc(d: i64, w: i64, seed: i64) -> *CountSketch {
51 if d < NX_CS_MIN_D { return 0 as *CountSketch }
52 if d > NX_CS_MAX_D { return 0 as *CountSketch }
53 if w < NX_CS_MIN_W { return 0 as *CountSketch }
54 if w > NX_CS_MAX_W { return 0 as *CountSketch }
55 if (w & (w - 1)) != 0 { return 0 as *CountSketch } // power of 2
56 let raw: *u8 = sys_mmap(48)
57 let c: *CountSketch = raw as *CountSketch
58 let cells: i64 = d * w
59 let cells_raw: *u8 = sys_mmap(cells * 8)
60 c.counters = cells_raw as *i64
61 var i: i64 = 0
62 while i < cells {
63 c.counters[i] = 0
64 i = i + 1
65 }
66 c.d = d
67 c.w = w
68 c.seed = seed
69 c.total = 0
70 return c
71}
72
73// === hash + sign helpers =========================================
74//
75// Kirsch-Mitzenmacher double-hashing: h_j(x) = (h1 + j*h2) & mask.
76// Sign: top bit of a separately-derived hash, mapped to ±1.
77
78func nx_cs_h1(c: *CountSketch, key: i64) -> i64 {
79 let mixed: i64 = (key * 0x9E3779B97F4A7C15 + c.seed) & 0xFFFFFFFFFFFFFFFF
80 return mixed & 0xFFFFFFFF
81}
82
83func nx_cs_h2(c: *CountSketch, key: i64) -> i64 {
84 let mixed: i64 = (key * 0xBF58476D1CE4E5B9 + c.seed) & 0xFFFFFFFFFFFFFFFF
85 return mixed & 0xFFFFFFFF
86}
87
88func nx_cs_column(c: *CountSketch, key: i64, j: i64) -> i64 {
89 let combined: i64 = (nx_cs_h1(c, key) + j * nx_cs_h2(c, key)) & 0xFFFFFFFF
90 return combined & (c.w - 1)
91}
92
93// Sign for row j: hash key+j and check the top bit.
94func nx_cs_sign(c: *CountSketch, key: i64, j: i64) -> i64 {
95 let mixed: i64 = ((key + j * 0x9E3779B9) * 0xC2B2AE3D27D4EB4F + c.seed) & 0xFFFFFFFFFFFFFFFF
96 if (mixed & (1 << 63)) == 0 { return 1 }
97 return -1
98}
99
100// === cell access =================================================
101
102func nx_cs_cell_idx(c: *CountSketch, j: i64, col: i64) -> i64 {
103 return j * c.w + col
104}
105
106// === add ==========================================================
107
108func nx_cs_add(c: *CountSketch, key: i64, count: i64) -> i64 {
109 if count == 0 { return 0 }
110 c.total = c.total + count
111 var j: i64 = 0
112 while j < c.d {
113 let col: i64 = nx_cs_column(c, key, j)
114 let sign: i64 = nx_cs_sign(c, key, j)
115 let idx: i64 = nx_cs_cell_idx(c, j, col)
116 c.counters[idx] = c.counters[idx] + sign * count
117 j = j + 1
118 }
119 return 0
120}
121
122// === query (median of signed reads) ==============================
123//
124// For each row j: signed_read = sign_j(key) * counter[j][h_j(key)]
125// Return median of d signed reads. Median is approximate median via
126// insertion-sort of small d.
127
128func nx_cs_estimate(c: *CountSketch, key: i64) -> i64 {
129 // Collect d signed reads.
130 let scratch_raw: *u8 = sys_mmap(c.d * 8)
131 let scratch: *i64 = scratch_raw as *i64
132 var j: i64 = 0
133 while j < c.d {
134 let col: i64 = nx_cs_column(c, key, j)
135 let sign: i64 = nx_cs_sign(c, key, j)
136 let idx: i64 = nx_cs_cell_idx(c, j, col)
137 scratch[j] = sign * c.counters[idx]
138 j = j + 1
139 }
140 // Insertion sort.
141 var i: i64 = 1
142 while i < c.d {
143 let cur: i64 = scratch[i]
144 var k: i64 = i - 1
145 var done: i64 = 0
146 while done == 0 {
147 if k < 0 { done = 1 }
148 if done == 0 {
149 if scratch[k] <= cur { done = 1 }
150 if done == 0 {
151 scratch[k + 1] = scratch[k]
152 k = k - 1
153 }
154 }
155 }
156 scratch[k + 1] = cur
157 i = i + 1
158 }
159 return scratch[c.d / 2]
160}
161
162// === typed envelope ===============================================
163//
164// Error bound is |est - f| <= ||f||_2 * sqrt(2/w) at confidence
165// (3/4)^(d/2). We declare a CONSERVATIVE absolute bound = total/sqrt(w)
166// (this is the worst case when L2 = total, i.e. one massive item).
167// param_a holds the bound; conf = (3/4)^(d/2) tabulated.
168
169func nx_cs_isqrt(x: i64) -> i64 { return vm_isqrt(x) }
170
171// Confidence depends on d: (3/4)^(d/2). Approximate by tabulating.
172func nx_cs_conf_ppb(d: i64) -> i64 {
173 if d <= 3 { return 562500000 } // (3/4)^1.5 = 0.65
174 if d <= 5 { return 421900000 } // (3/4)^2.5
175 if d <= 7 { return 316400000 } // (3/4)^3.5
176 if d <= 11 { return 177900000 } // (3/4)^5.5
177 return 100000000 // higher d converges
178}
179
180func nx_cs_query(c: *CountSketch, key: i64) -> *ApproxI64 {
181 let est: i64 = nx_cs_estimate(c, key)
182 let bound: i64 = c.total / nx_cs_isqrt(c.w)
183 // Returned envelope: 1e9 - conf_ppb confidence the bound holds;
184 // i.e. there's a small chance the estimate is further than `bound`.
185 return nx_approx_new(est, NX_ENV_ABS, bound,
186 1000000000 - nx_cs_conf_ppb(c.d),
187 NX_MATURITY_REFERENCE_IMPL,
188 NX_ADV_HONEST)
189}
190
191// === merge ========================================================
192
193func nx_cs_merge(a: *CountSketch, b: *CountSketch) -> *CountSketch {
194 if a.d != b.d { return 0 as *CountSketch }
195 if a.w != b.w { return 0 as *CountSketch }
196 if a.seed != b.seed { return 0 as *CountSketch }
197 let out: *CountSketch = nx_cs_alloc(a.d, a.w, a.seed)
198 let cells: i64 = a.d * a.w
199 var i: i64 = 0
200 while i < cells {
201 out.counters[i] = a.counters[i] + b.counters[i]
202 i = i + 1
203 }
204 out.total = a.total + b.total
205 return out
206}
207
208func nx_cs_memory_bytes(c: *CountSketch) -> i64 {
209 return 48 + c.d * c.w * 8
210}