You're building analytics for a URL shortener. You want to know which links get more than 1% of total clicks — but you're processing 10 billion clicks a day. Storing a counter per URL means hundreds of millions of entries. Most are hit once and never again. Lossy Counting gives you approximate frequencies with a provable error bound, using memory proportional to 1/ε instead of the number of distinct items.

The algorithm. Pick an error tolerance ε (say, 0.1%). Divide the stream into windows of size w = ⌈1/ε⌉. Maintain a table of (item, count, delta) triples, where delta is the maximum possible error for that item's count.

• When a new item arrives, if it's already in the table, increment its count.
• Otherwise, insert it with count = 1, delta = current_window - 1.
• At the end of each window, evict any entry where count + delta ≤ current_window.

Eviction is the "lossy" part — items that never got popular get purged. Items that arrived recently get a delta credit so they aren't unfairly evicted.

The guarantee. If an item's true frequency is f, its reported count is between f − εN and f, where N is total items seen. To find items with frequency ≥ s, query for those with count ≥ (s − ε)N. No false negatives — every frequent item is reported. False positives are bounded by ε.

Memory. Manku and Motwani proved worst-case space is O((1/ε) log(εN)). For ε = 0.001 and N = 10 billion, that's roughly 1/0.001 × log(10⁷) ≈ 23,000 entries. Compare to hundreds of millions of distinct URLs — three orders of magnitude smaller.

Real example. Streaming ad-fraud detection: you want IPs generating >0.01% of impressions. With ε = 0.001 and 100M impressions/hour, Lossy Counting uses ~14K entries and guarantees every abusive IP shows up. A hash map of raw counts would blow past 10M distinct IPs per hour.

Lossy Counting vs Space-Saving. Space-Saving uses fixed memory (k slots), always tracking exactly k candidates. Lossy Counting uses variable memory but gives tighter error bounds when the distribution is skewed. Rule of thumb: Space-Saving for "top-K" queries with a memory budget; Lossy Counting when you have an error budget and want all items above a threshold.

When it breaks. Uniform distributions — every item is roughly equally frequent, nothing gets evicted, and memory grows to the theoretical worst case. Lossy Counting shines on Zipfian data (web traffic, natural language, social networks), where the long tail evicts cleanly.