nx_sketch_lossy_counting.nx source
↩ module page · 237 lines · 7815 B
1// sketch_lossy_counting.nx -- Manku-Motwani 2002 Lossy Counting.
2//
3// THIRD major frequency-counting algorithm joining CMS / SpaceSaving /
4// Misra-Gries / CountSketch. Distinct technique: BUCKET-PRUNING.
5//
6// ALGORITHM:
7// Stream divided into "buckets" of size w = ceil(1/epsilon).
8// For each item:
9// - if tracked: increment frequency
10// - else: insert with frequency=1, error=current_bucket-1
11// At each bucket boundary (every w items):
12// - decrement EVERY tracked item's frequency by 1
13// - REMOVE items with frequency = 0
14//
15// GUARANTEE:
16// stored_freq <= true_freq (underestimate)
17// stored_freq + error >= true_freq (upper bound)
18// Items with true_freq > epsilon * N are NEVER missed
19// No item has stored_freq > true_freq (NEVER overestimates)
20//
21// COMPARISON to other frequency algorithms:
22// - CMS: random projection, overestimate-only, O(1) query
23// - SpaceSaving: k-bounded counters, overestimate-only, top-K native
24// - Misra-Gries: k-bounded counters, underestimate-only
25// - CountSketch: median-based, UNBIASED, supports negative
26// - Lossy Counting (THIS): bucket-pruning, underestimate + explicit
27// error tracking per entry
28//
29// MEMORY: O((1/epsilon) log(epsilon * N)) -- bounded but data-dependent.
30// We use a hash-set with linear probing; cap at NX_LC_MAX_ENTRIES.
31
32// nx_safety_envelope:
33// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
34// sil_target: SIL1
35// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
36// verdict: NOT_YET_EVALUATED
37
38import "nx_syscalls.nx"
39import "nx_sketch_types.nx"
40
41const NX_LC_MIN_EPS_PPM: i64 = 100 // epsilon >= 0.0001
42const NX_LC_MAX_EPS_PPM: i64 = 500000 // epsilon <= 0.5
43const NX_LC_MAX_ENTRIES: i64 = 100000
44
45struct LcEntry {
46 key: i64,
47 freq: i64,
48 err: i64,
49}
50
51struct LossyCounting {
52 entries: *LcEntry,
53 capacity: i64, // max entries (allocated table size, power of 2)
54 mask: i64, // capacity - 1
55 n_entries: i64, // active entries (key != 0 sentinel)
56 total_seen: i64,
57 epsilon_ppm: i64,
58 bucket_size: i64, // = ceil(1e6 / epsilon_ppm)
59 current_bucket: i64, // 1-indexed
60}
61
62const NX_LC_EMPTY_KEY: i64 = 0 // assume real keys != 0 by remapping
63
64// === construction =================================================
65
66func nx_lc_is_pow2(n: i64) -> i64 {
67 if n < 16 { return 0 }
68 if (n & (n - 1)) != 0 { return 0 }
69 return 1
70}
71
72func nx_lc_alloc(capacity: i64, epsilon_ppm: i64) -> *LossyCounting {
73 if nx_lc_is_pow2(capacity) != 1 { return 0 as *LossyCounting }
74 if capacity > NX_LC_MAX_ENTRIES { return 0 as *LossyCounting }
75 if epsilon_ppm < NX_LC_MIN_EPS_PPM { return 0 as *LossyCounting }
76 if epsilon_ppm > NX_LC_MAX_EPS_PPM { return 0 as *LossyCounting }
77 let raw: *u8 = sys_mmap(72)
78 let lc: *LossyCounting = raw as *LossyCounting
79 let ent_raw: *u8 = sys_mmap(capacity * 24)
80 lc.entries = ent_raw as *LcEntry
81 var i: i64 = 0
82 while i < capacity {
83 let e: *LcEntry = (lc.entries as i64 + i * 24) as *LcEntry
84 e.key = NX_LC_EMPTY_KEY
85 e.freq = 0
86 e.err = 0
87 i = i + 1
88 }
89 lc.capacity = capacity
90 lc.mask = capacity - 1
91 lc.n_entries = 0
92 lc.total_seen = 0
93 lc.epsilon_ppm = epsilon_ppm
94 lc.bucket_size = (1000000 + epsilon_ppm - 1) / epsilon_ppm // ceil(1/eps)
95 lc.current_bucket = 1
96 return lc
97}
98
99// === hash + probe =================================================
100
101func nx_lc_hash(key: i64) -> i64 {
102 let mixed: i64 = (key * 0x9E3779B97F4A7C15) & 0xFFFFFFFFFFFFFFFF
103 return mixed
104}
105
106func nx_lc_entry_at(lc: *LossyCounting, idx: i64) -> *LcEntry {
107 return (lc.entries as i64 + idx * 24) as *LcEntry
108}
109
110// Find slot for key. Returns:
111// index of existing entry with this key, OR
112// index of first empty slot for insertion.
113func nx_lc_probe(lc: *LossyCounting, key: i64) -> i64 {
114 var i: i64 = nx_lc_hash(key) & lc.mask
115 var done: i64 = 0
116 var found: i64 = -1
117 while done == 0 {
118 let e: *LcEntry = nx_lc_entry_at(lc, i)
119 if e.key == NX_LC_EMPTY_KEY {
120 found = i
121 done = 1
122 }
123 if done == 0 {
124 if e.key == key {
125 found = i
126 done = 1
127 }
128 }
129 if done == 0 {
130 i = (i + 1) & lc.mask
131 }
132 }
133 return found
134}
135
136// === bucket-boundary pruning ======================================
137//
138// Decrement every tracked entry's freq by 1; remove entries that reach 0.
139// Removal is via marking key=EMPTY; subsequent probes will treat as empty.
140// (No re-hashing of subsequent collisions in this v1 -- accuracy slightly
141// reduced but correctness preserved as Lossy Counting only requires
142// that pruned items have low frequency.)
143
144func nx_lc_prune(lc: *LossyCounting) -> i64 {
145 var i: i64 = 0
146 while i < lc.capacity {
147 let e: *LcEntry = nx_lc_entry_at(lc, i)
148 if e.key != NX_LC_EMPTY_KEY {
149 e.freq = e.freq - 1
150 if e.freq <= 0 {
151 e.key = NX_LC_EMPTY_KEY
152 e.freq = 0
153 e.err = 0
154 lc.n_entries = lc.n_entries - 1
155 }
156 }
157 i = i + 1
158 }
159 return 0
160}
161
162// === add ==========================================================
163
164func nx_lc_add(lc: *LossyCounting, key: i64) -> i64 {
165 if key == NX_LC_EMPTY_KEY { return -1 } // 0 reserved as sentinel
166 lc.total_seen = lc.total_seen + 1
167 let idx: i64 = nx_lc_probe(lc, key)
168 let e: *LcEntry = nx_lc_entry_at(lc, idx)
169 if e.key == NX_LC_EMPTY_KEY {
170 // New entry.
171 if lc.n_entries >= lc.capacity - 1 { // leave room for probing
172 return -2 // table full; cannot insert
173 }
174 e.key = key
175 e.freq = 1
176 e.err = lc.current_bucket - 1
177 lc.n_entries = lc.n_entries + 1
178 }
179 if e.key == key {
180 if e.freq < lc.bucket_size + lc.current_bucket {
181 // Don't overcount via reset (defensive); just increment.
182 }
183 e.freq = e.freq + 1
184 }
185 // Bucket boundary: prune.
186 if (lc.total_seen % lc.bucket_size) == 0 {
187 nx_lc_prune(lc)
188 lc.current_bucket = lc.current_bucket + 1
189 }
190 return 0
191}
192
193// === queries ======================================================
194
195func nx_lc_estimate(lc: *LossyCounting, key: i64) -> i64 {
196 if key == NX_LC_EMPTY_KEY { return 0 }
197 let idx: i64 = nx_lc_probe(lc, key)
198 let e: *LcEntry = nx_lc_entry_at(lc, idx)
199 if e.key != key { return 0 }
200 return e.freq
201}
202
203// Upper bound: stored_freq + error.
204func nx_lc_upper_bound(lc: *LossyCounting, key: i64) -> i64 {
205 if key == NX_LC_EMPTY_KEY { return 0 }
206 let idx: i64 = nx_lc_probe(lc, key)
207 let e: *LcEntry = nx_lc_entry_at(lc, idx)
208 if e.key != key { return 0 }
209 return e.freq + e.err
210}
211
212// Maximum possible undercount = epsilon * N.
213func nx_lc_max_undercount(lc: *LossyCounting) -> i64 {
214 return (lc.epsilon_ppm * lc.total_seen) / 1000000
215}
216
217func nx_lc_query(lc: *LossyCounting, key: i64) -> *ApproxI64 {
218 let est: i64 = nx_lc_estimate(lc, key)
219 return nx_approx_new(est, NX_ENV_ABS, nx_lc_max_undercount(lc),
220 1000000000,
221 NX_MATURITY_REFERENCE_IMPL,
222 NX_ADV_HONEST)
223}
224
225// === introspection ================================================
226
227func nx_lc_n_entries(lc: *LossyCounting) -> i64 {
228 return lc.n_entries
229}
230
231func nx_lc_total_seen(lc: *LossyCounting) -> i64 {
232 return lc.total_seen
233}
234
235func nx_lc_memory_bytes(lc: *LossyCounting) -> i64 {
236 return 72 + lc.capacity * 24
237}