Module sparse 

Sparse HyperLogLog encoding for low-cardinality streams. Stores a Vec<(register_index, rho)> until the entry count crosses a configured threshold, then promotes itself into a dense HyperLogLog register array. Hot paths beyond promotion are the same as the base.

Why this exists: a default p=14 HLL allocates 16 KB for the register array even when it has seen zero items. For pipelines that maintain millions of small sketches keyed by tenant / customer / shard, 16 KB per sketch quickly dominates memory. Sparse mode starts at zero payload and grows five bytes per distinct register touched, until the dense array stops being an over-allocation.

Crossover threshold defaults to m / 4 entries. Past that, the sparse list is past dense’s memory cost without dense’s O(1) lookup, so promotion is the right move. Promotion is one-way - we never go back from dense to sparse.

This is the plain pair-list encoding, not HLL++’s. Heule et al. store the sparse pairs at a higher temporary precision and difference-encode them as varints behind a small unsorted temp set; that buys accuracy and bytes at low cardinality and costs a merge step on every flush. Neither is implemented here.

Structs

SparseHyperLogLog

HyperLogLog variant that holds a compact (idx, rho) pair list at low cardinality and promotes to a dense register array once the list grows past a threshold.