sketch_lossy_counting.nx

sketch_lossy_counting.nx -- Manku-Motwani 2002 Lossy Counting. THIRD major frequency-counting algorithm joining CMS / SpaceSaving / Misra-Gries / CountSketch. Distinct technique: BUCKET-PRUNING. ALGORITHM: Stream divided into "buckets" of size w = ceil(1/epsilon). For each item: - if tracked: increment frequency - else: insert with frequency=1, error=current_bucket-1 At each bucket boundary (every w items): - decrement EVERY tracked item's frequency by 1 - REMOVE items with frequency = 0 GUARANTEE: stored_freq <= true_freq (underestimate) stored_freq + error >= true_freq (upper bound) Items with true_freq > epsilon * N are NEVER missed No item has stored_freq > true_freq (NEVER overestimates) COMPARISON to other frequency algorithms: - CMS: random projection, overestimate-only, O(1) query - SpaceSaving: k-bounded counters, overestimate-only, top-K native - Misra-Gries: k-bounded counters, underestimate-only - CountSketch: median-based, UNBIASED, supports negative - Lossy Counting (THIS): bucket-pruning, underestimate + explicit error tracking per entry MEMORY: O((1/epsilon) log(epsilon * N)) -- bounded but data-dependent. We use a hash-set with linear probing; cap at NX_LC_MAX_ENTRIES.