← Back

I Built a Data Structure That Doesn't Exist in Any Textbook

And why "what's hot right now?" is harder than it sounds.

April 5, 2026 · ~8 min read

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.

The Problem

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.

How HeatMap Works

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).

OperationComplexity
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.

The Formal Guarantees

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.

How I Tested It

I tested against four baselines on realistic workloads:

  1. Count-Min Sketch — the standard frequency sketch, no decay
  2. Space-Saving — classic top-k tracker, no decay
  3. Sliding Window — fixed-size time window counter
  4. Exact Decayed Counter — brute-force ground truth (for validation)

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.

Twitter trending detection

(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.

API bot detection

(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.

Cache hit prediction

(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.

Optimality at a Glance

MetricLower BoundHeatMapOptimal?
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.

Why It Matters

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.

Try It

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.

Disclaimer: The views, work, and opinions expressed in this article are entirely my own. This project was developed independently on personal time, using personal resources. No proprietary information, insights, or resources from any employer — including Capital One — were used in the research, development, or writing of this article.