And why "what's hot right now?" is harder than it sounds.
Every computer science student learns the classics. Bloom filters tell you if something might be in a set. Count-Min Sketch gives you approximate frequencies. HyperLogLog counts unique items. Space-Saving tracks your top-k.
These are elegant, well-studied, and deeply useful. But a few years ago, I kept running into a question none of them answered cleanly:
What's popular right now?
Not what was popular yesterday. Not the all-time count. What's trending at this exact moment.
There are approximations — sliding windows, decayed counters bolted onto Count-Min Sketch, exponential moving averages computed ad-hoc. But no widely-adopted data structure treats temporal heat as a first-class concept with formal guarantees, a clean API, and proven optimality.
So I built one. I call it HeatMap.
Imagine you're building a trending topics engine. A user searches for "ChatGPT" 1,000 times over the past month, and "GPT-5" 200 times in the last hour. Which one is actually trending?
A simple counter says ChatGPT. Every intuition says GPT-5.
The difference isn't frequency — it's recency weighted by frequency. Old observations should decay. New ones should carry more weight. The mathematical answer is elegant:
dH/dt = -λ·H + δ(item)
This is the heat equation from physics, repurposed. Every item has a temperature H that naturally decays over time (rate λ), and spikes when the item is observed (impulse δ). The solution:
H(t) = H(t₀)·e^(-λ(t-t₀)) + Σ e^(-λ(t-tᵢ))
Each observation contributes heat, and that contribution decays exponentially. A "half-life" parameter controls how quickly things cool down. Set it to 60 seconds, and an observation from a minute ago is worth half its original value. Set it to 24 hours, and yesterday's spike still matters.
This isn't a new idea — exponential moving averages are ancient. The gap is that nobody has formalized this as a sketch primitive with error bounds that account for the interaction between decay and hash collisions, then proven it's space-time optimal.
HeatMap combines the decay model with the Count-Min Sketch paradigm — giving you sublinear space with probabilistic guarantees.
from heatmap_sketch import HeatMap
hm = HeatMap(half_life_seconds=60.0)
hm.add("GPT-5") # Heat spikes
hm.add("ChatGPT") # Gets some heat too
hm.check("GPT-5") # Returns current heat value
hm.top(10) # Returns 10 hottest items right now
hm.stop() # Clean up background decay thread
The structure uses k hash functions to map items into m counter slots. Each slot stores a float — the current heat value. A background thread periodically multiplies all counters by the decay factor α = e(-λΔt).
| Operation | Complexity |
|---|---|
| add(x) | O(log(1/δ)) |
| check(x) | O(log(1/δ)) |
| decay() | O(n/ε) or O(1) amortized with lazy decay |
| top(k) | O(|C| log k) |
Where n is the number of distinct items, ε is the error tolerance, and δ is the failure probability.
This is where HeatMap differs from "just add decay to Count-Min." The key results:
Overestimate property: For any item x, the estimate Ĥ(x) ≥ H(x) always. HeatMap never undercounts. (Same as Count-Min, but it holds through decay operations — not just adds.)
Bounded error: With probability ≥ 1 − δ, the error is ≤ ε · total_heat for all items simultaneously. The proof accounts for how decay interacts with collision noise — decay actually helps by shrinking stale collision contributions.
Space optimality: HeatMap uses O((n/ε) · log(1/δ)) space, matching the information-theoretic lower bound (proven via reduction from the INDEX problem in communication complexity) within a constant factor of ~2×.
Time optimality: O(log(1/δ)) per query — matching the cell-probe lower bound. Add, check, and query are all optimal.
Space-time tradeoff: For constant ε, HeatMap achieves the optimal space × query_time product of O(n · log(1/δ)).
None of these results exist for "Count-Min with ad-hoc decay" because nobody proved them.
I tested against four baselines on realistic workloads:
The ground truth for "what's actually trending" uses the same exponential decay formula as HeatMap, computed exactly over all observations. This matters — comparing a decay-based structure against a static counter as "truth" tells you nothing.
(100K tweets, 10K hashtags, 5-min half-life)
HeatMap achieved 99.6% recall@10 and 99.6% precision@10 against the exact decayed ground truth — nearly identifying all 10 currently-bursting hashtags at each checkpoint. Count-Min Sketch and Space-Saving, having no concept of time, were dominated by all-time popular topics that weren't actually trending. The sliding window worked reasonably but required tuning the window size to match the half-life — change the timescale and it breaks. Processed 154K tweets/sec.
(200K requests, mixed human/bot traffic, 1-min half-life)
100% precision — zero false positives. The decay model detected 95.8% of bot traffic, cleanly separating bursty patterns from steady human use. A legitimate user making 2 requests/minute has a low, stable heat. A bot making 100 requests in 10 seconds spikes dramatically. The decay acts as a natural rate limiter — past burstiness fades. Processed 127K requests/sec.
(500K accesses, working set shifts, 5-min half-life)
99.2% precision@100 and recall@100 against the exact decayed ground truth. HeatMap's top-100 recommendations for what to keep in cache matched what was genuinely hot right now. Items that used to be popular but stopped being accessed dropped out naturally — something a static frequency counter never does.
| Metric | Lower Bound | HeatMap | Optimal? |
|---|---|---|---|
| Space | Ω((n/ε)·log(1/δ)) | O((n/ε)·log(1/δ)) | ✅ Within 2× |
| Query time | Ω(log(1/δ)) | O(log(1/δ)) | ✅ Exact |
| Add time | Ω(log(1/δ)) | O(log(1/δ)) | ✅ Exact |
| Decay time | Ω(n/ε) | O(n/ε) or O(1)* | ✅ With lazy |
*Lazy decay achieves O(1) amortized when access rate ≪ 1/Δt.
The difference between HeatMap and "just use a decayed counter" is the difference between a hashmap and a hash table — sure, you can implement one with the other, but the formal guarantees, the optimality proofs, and the standard API are what make it a primitive.
Existing structures answer nouns: "is it there?" "how many?" "how many unique?" HeatMap answers a verb: "what's trending?" And it does so with provably optimal space and time.
pip install heatmap-sketch
GitHub · PyPI · 168 tests, zero dependencies, MIT license.
The full formal analysis — including all proofs, optimality bounds, and benchmark methodology — is available in the repository.