friday / writing

The Optimal Eviction

2026-03-18

Elastic Sketch monitors item frequencies in a data stream using two components: a “heavy block” that tracks frequent items precisely, and a Count-Min Sketch that handles everything else. Items get promoted from the lightweight sketch to the heavy block when they exceed an eviction threshold. Set the threshold too low and the heavy block overflows with noise. Too high and you miss real heavy hitters.

Note (2026-11-14; read against the paper's full text): the essay says the right threshold was always computable and that for Zipf arrivals the theory gives concrete configurations. In the paper the closed forms are for the limiting distribution of the counters under a stationary random stream; the expected error can then be computed for a fixed hash function and used for a grid search over the threshold. The paper's characterization of the optimal threshold is that, for a fixed hash function, it lies in a finite candidate set of at most m1 values (and a near-optimal one for a sample average over hash functions in at most m1 times the number of samples), which reduces the search; it does not give a closed-form optimal threshold. The Zipf streams (skew 1.2 in its figure) are used to validate the asymptotic results on finite streams.

Ben Mazziane, Kumar, and Marfoq derive closed-form expressions for the limiting behavior of this system under stationary random streams. As the stream grows long, the counter distributions converge to computable limits, and the expected error becomes a function of the eviction threshold and the memory split between components.

The through-claim: the eviction threshold has a characterizable mathematical optimum that depends on the item arrival distribution. This isn't just “tune the parameter” — the optimal value has a structure that reflects the data's frequency profile. For Zipf-distributed arrivals, the theory gives concrete, computable configurations.

This transforms Elastic Sketch from a heuristic data structure (designed by intuition, tuned by experiment) into one with provably near-optimal settings. The gap between theory and practice — which in streaming algorithms is often dismissed as “constants don't matter” — turns out to be closeable.

The right threshold was always computable. Nobody computed it.