nx_sketch_count_sketch.nx source
↩ module page · 224 lines · 7502 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"
33
34const NX_CS_MIN_D: i64 = 3
35const NX_CS_MAX_D: i64 = 32
36const NX_CS_MIN_W: i64 = 64
37const NX_CS_MAX_W: i64 = 65536
38
39struct CountSketch {
40 counters: *i64, // d * w grid, in i64 (signed)
41 d: i64,
42 w: i64,
43 seed: i64,
44 total: i64,
45}
46
47// === construction =================================================
48
49func nx_cs_alloc(d: i64, w: i64, seed: i64) -> *CountSketch {
50 if d < NX_CS_MIN_D { return 0 as *CountSketch }
51 if d > NX_CS_MAX_D { return 0 as *CountSketch }
52 if w < NX_CS_MIN_W { return 0 as *CountSketch }
53 if w > NX_CS_MAX_W { return 0 as *CountSketch }
54 if (w & (w - 1)) != 0 { return 0 as *CountSketch } // power of 2
55 let raw: *u8 = sys_mmap(48)
56 let c: *CountSketch = raw as *CountSketch
57 let cells: i64 = d * w
58 let cells_raw: *u8 = sys_mmap(cells * 8)
59 c.counters = cells_raw as *i64
60 var i: i64 = 0
61 while i < cells {
62 c.counters[i] = 0
63 i = i + 1
64 }
65 c.d = d
66 c.w = w
67 c.seed = seed
68 c.total = 0
69 return c
70}
71
72// === hash + sign helpers =========================================
73//
74// Kirsch-Mitzenmacher double-hashing: h_j(x) = (h1 + j*h2) & mask.
75// Sign: top bit of a separately-derived hash, mapped to ±1.
76
77func nx_cs_h1(c: *CountSketch, key: i64) -> i64 {
78 let mixed: i64 = (key * 0x9E3779B97F4A7C15 + c.seed) & 0xFFFFFFFFFFFFFFFF
79 return mixed & 0xFFFFFFFF
80}
81
82func nx_cs_h2(c: *CountSketch, key: i64) -> i64 {
83 let mixed: i64 = (key * 0xBF58476D1CE4E5B9 + c.seed) & 0xFFFFFFFFFFFFFFFF
84 return mixed & 0xFFFFFFFF
85}
86
87func nx_cs_column(c: *CountSketch, key: i64, j: i64) -> i64 {
88 let combined: i64 = (nx_cs_h1(c, key) + j * nx_cs_h2(c, key)) & 0xFFFFFFFF
89 return combined & (c.w - 1)
90}
91
92// Sign for row j: hash key+j and check the top bit.
93func nx_cs_sign(c: *CountSketch, key: i64, j: i64) -> i64 {
94 let mixed: i64 = ((key + j * 0x9E3779B9) * 0xC2B2AE3D27D4EB4F + c.seed) & 0xFFFFFFFFFFFFFFFF
95 if (mixed & (1 << 63)) == 0 { return 1 }
96 return -1
97}
98
99// === cell access =================================================
100
101func nx_cs_cell_idx(c: *CountSketch, j: i64, col: i64) -> i64 {
102 return j * c.w + col
103}
104
105// === add ==========================================================
106
107func nx_cs_add(c: *CountSketch, key: i64, count: i64) -> i64 {
108 if count == 0 { return 0 }
109 c.total = c.total + count
110 var j: i64 = 0
111 while j < c.d {
112 let col: i64 = nx_cs_column(c, key, j)
113 let sign: i64 = nx_cs_sign(c, key, j)
114 let idx: i64 = nx_cs_cell_idx(c, j, col)
115 c.counters[idx] = c.counters[idx] + sign * count
116 j = j + 1
117 }
118 return 0
119}
120
121// === query (median of signed reads) ==============================
122//
123// For each row j: signed_read = sign_j(key) * counter[j][h_j(key)]
124// Return median of d signed reads. Median is approximate median via
125// insertion-sort of small d.
126
127func nx_cs_estimate(c: *CountSketch, key: i64) -> i64 {
128 // Collect d signed reads.
129 let scratch_raw: *u8 = sys_mmap(c.d * 8)
130 let scratch: *i64 = scratch_raw as *i64
131 var j: i64 = 0
132 while j < c.d {
133 let col: i64 = nx_cs_column(c, key, j)
134 let sign: i64 = nx_cs_sign(c, key, j)
135 let idx: i64 = nx_cs_cell_idx(c, j, col)
136 scratch[j] = sign * c.counters[idx]
137 j = j + 1
138 }
139 // Insertion sort.
140 var i: i64 = 1
141 while i < c.d {
142 let cur: i64 = scratch[i]
143 var k: i64 = i - 1
144 var done: i64 = 0
145 while done == 0 {
146 if k < 0 { done = 1 }
147 if done == 0 {
148 if scratch[k] <= cur { done = 1 }
149 if done == 0 {
150 scratch[k + 1] = scratch[k]
151 k = k - 1
152 }
153 }
154 }
155 scratch[k + 1] = cur
156 i = i + 1
157 }
158 return scratch[c.d / 2]
159}
160
161// === typed envelope ===============================================
162//
163// Error bound is |est - f| <= ||f||_2 * sqrt(2/w) at confidence
164// (3/4)^(d/2). We declare a CONSERVATIVE absolute bound = total/sqrt(w)
165// (this is the worst case when L2 = total, i.e. one massive item).
166// param_a holds the bound; conf = (3/4)^(d/2) tabulated.
167
168func nx_cs_isqrt(x: i64) -> i64 {
169 if x < 0 { return 0 }
170 if x == 0 { return 0 }
171 if x < 4 { return 1 }
172 var g: i64 = (x >> 1) + 1
173 var iter: i64 = 0
174 while iter < 64 {
175 let next_g: i64 = (g + x / g) / 2
176 if next_g >= g { iter = 64 }
177 if next_g < g {
178 g = next_g
179 iter = iter + 1
180 }
181 }
182 return g
183}
184
185// Confidence depends on d: (3/4)^(d/2). Approximate by tabulating.
186func nx_cs_conf_ppb(d: i64) -> i64 {
187 if d <= 3 { return 562500000 } // (3/4)^1.5 = 0.65
188 if d <= 5 { return 421900000 } // (3/4)^2.5
189 if d <= 7 { return 316400000 } // (3/4)^3.5
190 if d <= 11 { return 177900000 } // (3/4)^5.5
191 return 100000000 // higher d converges
192}
193
194func nx_cs_query(c: *CountSketch, key: i64) -> *ApproxI64 {
195 let est: i64 = nx_cs_estimate(c, key)
196 let bound: i64 = c.total / nx_cs_isqrt(c.w)
197 // Returned envelope: 1e9 - conf_ppb confidence the bound holds;
198 // i.e. there's a small chance the estimate is further than `bound`.
199 return nx_approx_new(est, NX_ENV_ABS, bound,
200 1000000000 - nx_cs_conf_ppb(c.d),
201 NX_MATURITY_REFERENCE_IMPL,
202 NX_ADV_HONEST)
203}
204
205// === merge ========================================================
206
207func nx_cs_merge(a: *CountSketch, b: *CountSketch) -> *CountSketch {
208 if a.d != b.d { return 0 as *CountSketch }
209 if a.w != b.w { return 0 as *CountSketch }
210 if a.seed != b.seed { return 0 as *CountSketch }
211 let out: *CountSketch = nx_cs_alloc(a.d, a.w, a.seed)
212 let cells: i64 = a.d * a.w
213 var i: i64 = 0
214 while i < cells {
215 out.counters[i] = a.counters[i] + b.counters[i]
216 i = i + 1
217 }
218 out.total = a.total + b.total
219 return out
220}
221
222func nx_cs_memory_bytes(c: *CountSketch) -> i64 {
223 return 48 + c.d * c.w * 8
224}