nx_sketch_cpc.nx

sketch_cpc.nx -- CPC sparse-mode cardinality sketch (Lang 2017 / FM85). "Back to the Future: An Even More Nearly Optimal Cardinality Estimation Algorithm" -- arXiv:1708.06839. CPC is the headline cardinality stomp over HLL: same memory, tighter rel-stddev via the HIP estimator. THIS V1 SHIPS THE SPARSE MODE + HIP ESTIMATOR: - sparse mode: store coupons in a hash set until capacity reached - HIP estimator: kappa accumulates 1/theta on every distinct coupon DENSE MODE (pinned + sliding) queued for v2. Sparse mode alone is sufficient for cardinalities up to ~K coupons (typical K=4096 -> exact for n < ~3000, then accurate-via-HIP up to ~tens-of-thousands). COUPON DERIVATION: hash(key) -> 64-bit value column = (hash >> 32) & (m - 1) (high bits choose register column) row = clz32(hash & 0xFFFFFFFF) + 1 (low bits drive rho, capped at w) coupon_id = column * w + row (unique pair encoding) HIP ESTIMATOR (Cohen 2015, Lang 2017): For each distinct coupon arrival i (0..n-1): theta_i = (M - i) / M where M = m * w (total possible coupons) kappa += 1 / theta_i = M / (M - i) estimate = kappa At i = 0 (first coupon): theta = 1.0; kappa += 1. At i = M-1: theta = 1/M; kappa += M. COMPLEMENTS the cardinality family: - HLL/LC/KMV/Theta: classical estimators, lots of variance - CPC (this): HIP-based, near-optimal variance via online accounting COMPOSES against sketch_hash_map for sparse coupon storage. LOSSLESS-LANGUAGE DISCIPLINE: estimate has rel_stddev approx 1/sqrt(M) at confidence 0.6827. For m=128, w=32 (M=4096): ~1.56% rel. For HLL_8 lg_k=7 (m=128): ~9.2% rel. CPC stomp ~6x improvement.