You've got a stream of a billion events an hour — API calls, ad impressions, DNS queries. You want to know which keys account for more than, say, 1% of traffic. You can't store every key. Lossy Counting gives you deterministic error bounds but scans in fixed-size batches. Sticky Sampling takes a different bet: use randomness to decide what to remember, and you get probabilistic guarantees with a smaller memory footprint on average.

The algorithm, from Manku and Motwani (2002):

• Pick a support threshold s (e.g., 0.01 = 1%), error ε (e.g., 0.001), and failure probability δ (e.g., 0.0001).
• Compute sampling rate r. Early in the stream, r = 1 (keep everything). As the stream grows, r increases geometrically — after t = 2t/ε items, r doubles.
• For each incoming item: if it's in the table, increment. Otherwise, sample it with probability 1/r. When r doubles, walk the table and for each entry, flip a coin per unit of count — decrement on tails, delete if it hits zero.
• At query time, report entries with count ≥ (s − ε)N.

Concrete example: You're building an anti-abuse system watching 100M DNS queries per hour. You want domains representing ≥1% of traffic (heavy abuse candidates), tolerating 0.1% error, with 99.99% confidence. Expected table size: (1/ε) · log(1/(s·δ)) ≈ 1000 · log(10,000) ≈ ~9,200 entries. Compare that to Lossy Counting's (1/ε) · log(εN) ≈ 1000 · log(100,000) ≈ ~11,500 entries — Sticky Sampling wins for large N because its bound doesn't grow with stream length.

The rule of thumb: Sticky Sampling's expected memory is independent of N once the stream is large enough. Lossy Counting's grows as log(N). If your stream is unbounded (think: forever-running telemetry pipeline), Sticky Sampling amortizes better. If you need hard worst-case guarantees, Lossy Counting's deterministic error is safer.

The catch is the coin-flip resampling pass — it's O(table size) each time r doubles, which happens O(log N) times total. So amortized cost stays low, but you'll see occasional latency spikes. In practice, run the resampling on a background thread and let the table be slightly stale for a few milliseconds.

Use it when: you're monitoring a long-running stream, you can tolerate probabilistic guarantees, and memory matters more than worst-case predictability.