sketch_linear_counter.nx

sketch_linear_counter.nx -- Linear Counting (Whang-Vander Zanden 1990). Pre-HLL cardinality primitive. Simpler than HLL; sometimes more accurate at small cardinalities (n < m/10). Used by Google's BigQuery as the small-cardinality fallback. ALGORITHM: bitmap of m bits, all zero initially. add(x): set bit at index = hash(x) % m estimate(n) = -m * ln(zeros / m) where zeros = count of unset bits at query time. Derivation: if items are hashed uniformly to m buckets and we observe `zeros` empty buckets, then by occupancy theory the true count n satisfies E[zeros] = m * (1 - 1/m)^n ≈ m * e^(-n/m) inverting: n ≈ -m * ln(zeros / m). CAPABILITIES (vs HLL): - LC: accurate at n < m (uses bitmap directly) - HLL: accurate at n >> m (uses harmonic mean of register maxima) Together: BigQuery + others run LC for n < threshold, HLL for n >=. INTEGER-FIXED-POINT IMPLEMENTATION: ln(zeros/m) approximated via tabulated values keyed on (zeros*100)/m (percentage of empty bits, in [0, 100]). Table values are -ln(p/100) * 1_000_000 in PPM (negative of -log so positive). MEMORY: m bits = m/8 bytes. For m=8192: 1 KB. LOSSLESS-LANGUAGE DISCIPLINE: nx_lc_query returns ApproxI64 with NX_ENV_REL_STDDEV. Standard error per Whang 1990: sqrt(e^t - t - 1) / t where t = n/m (load). Tabulated by load class.