LOSSY COUNTING the frequent items of an endless stream, in bounded counters
Which items appear often in a stream too large to store? Lossy Counting keeps a bounded set of (item, count) entries and periodically sweeps out the ones whose counts have fallen behind — guaranteeing every truly-frequent item survives, while rare ones are forgotten. It gives an error bound, not exact counts: a frequency may be undercounted by at most a controlled slack. A correct exact frequency table must hold every distinct item ever seen; Lossy Counting holds only the plausibly-frequent, in memory bounded by the error you tolerate. The forgetting is deliberate and quantified — the “lossy” is the point.
THE TECHNIQUE bounded (item,count) entries; sweep out the laggards periodically
A stream with one frequent value. The demo tallies with bounded counters and reports the heavy hitter's count: live demo
HISTORY & CREDIT Manku & Motwani, 2002 · VLDB
“Frequent-item counting needs a slot per distinct item.” — Lossy Counting keeps only the plausibly-frequent and sweeps the rest, with a provable error bound: bounded memory, guaranteed to keep the heavy hitters. cited
2002 · Gurmeet Singh Manku & Rajeev Motwani — “Approximate Frequency Counts over Data Streams,” VLDB: Lossy Counting and Sticky Sampling. kin · the Misra–Gries summary (1982) and Space-Saving (2005) — the frequent-items family. now · heavy-hitter detection in network monitoring, databases, and log analytics.
Counters for the many, kept only for the frequent; the laggards swept away on a schedule. Bounded memory with a bound on the error, too. Manku-Motwani 2002
RECOMMEND FOR I-13 the heavy hitter's tally, on the compiler
On the canonical compiler, the frequent value 3 in the stream [3,3,1,3,2,3] tallies to 4 — above a threshold of 2, surviving any sweep:
$ i13 run op_lossy.i13 # bounded counters -> the heavy hitter's count
RUN OK · 181 step(s) · peak stack 7 · call depth 7
hh_count = 4 -- item 3 survives; rare items would be swept out
Recommend: Lossy Counting is forgetting with a warranty — it discards rare items but proves the frequent ones survive, in memory bounded by a chosen error. i13 tallies the heavy hitter 3 to 4. The supplement to correctness: a correct exact frequency table stores every distinct item; this stores only the plausibly-frequent. Not a keeper — the memory bound is again a resource/accuracy trade, kin to Kahan's accounting more than a new structural axis — but a canonical streaming instrument and the natural companion to Morris and Frugal in the sketch corner of the batch.