Exponential Histograms

Imagine a web server logging millions of requests per second. You want to know: how many errors occurred in the last five minutes? Storing every timestamp is impractical — the stream never ends, and memory is finite.

This is the sliding-window counting problem: maintain a count of events that arrived within the last $N$ time steps, using as little memory as possible, while answering queries at any moment.

The naive solution keeps a list of all recent timestamps. It is exact, but it uses $O(N)$ space — and $N$ can be enormous. Can we do better? In 2002, Datar, Gionis, Indyk, and Motwani showed the answer is yes: you can count within a $(1+\varepsilon)$ factor of the true count using only $O\!\left(\frac{1}{\varepsilon} \log^2 N\right)$ bits of space. The key idea is the exponential histogram — a summary that groups events into exponentially-growing buckets instead of remembering each one.

The demo below maintains an exponential histogram over a stream of events arriving one at a time. Each event is represented as a bucket of size 1. When too many same-sized buckets accumulate, two are merged into one bucket of double the size. Buckets that fall outside the sliding window are discarded.

<!-- {{c_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="controls">
  <button id="btn-add" type="button">{{btn_add}}</button>
  <button id="btn-stream" type="button">{{btn_stream}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <label class="param-label">{{label_window}}
    <input id="inp-window" type="number" min="8" max="128" value="32" />
  </label>
  <label class="param-label">{{label_epsilon}}
    <input id="inp-eps" type="number" min="0.05" max="0.5" step="0.05" value="0.25" />
  </label>
</div>
<div class="stats-row">
  <span class="stat-box"><span class="stat-label">{{label_true}}</span><span id="true-count" class="stat-val">0</span></span>
  <span class="stat-box"><span class="stat-label">{{label_est}}</span><span id="est-count" class="stat-val">0</span></span>
  <span class="stat-box"><span class="stat-label">{{label_error}}</span><span id="error-pct" class="stat-val">—</span></span>
  <span class="stat-box"><span class="stat-label">{{label_buckets}}</span><span id="bucket-count" class="stat-val">0</span></span>
</div>
<div class="timeline-wrap">
  <canvas id="timeline" width="480" height="48"></canvas>
</div>
<div id="bucket-vis" class="bucket-vis"></div>
<div id="status" class="status"></div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.5; }
.controls { display: flex; flex-wrap: wrap; gap: .4rem; align-items: center; margin-bottom: .55rem; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.param-label { font-size: .82rem; color: #555; display: flex; align-items: center; gap: .3rem; }
.param-label input { width: 60px; border: 1px solid #bbb; border-radius: 5px; padding: 2px 5px; font-size: .82rem; }
.stats-row { display: flex; flex-wrap: wrap; gap: .4rem; margin-bottom: .5rem; }
.stat-box { background: #eef2f6; border-radius: 7px; padding: .3rem .7rem; display: flex; flex-direction: column; align-items: center; min-width: 72px; }
.stat-label { font-size: .72rem; color: #666; text-transform: uppercase; letter-spacing: .03em; }
.stat-val { font: 700 1.15rem ui-monospace, monospace; color: #1d3557; }
.timeline-wrap { margin-bottom: .5rem; }
#timeline { border-radius: 6px; background: #f4f6f8; display: block; max-width: 100%; }
.bucket-vis { display: flex; flex-wrap: wrap; gap: 5px; min-height: 38px; margin-bottom: .4rem; align-items: flex-end; }
.bucket { display: flex; align-items: center; justify-content: center;
          border-radius: 5px; color: #fff; font: 700 11px ui-monospace, monospace;
          transition: width .15s, opacity .15s; min-width: 22px; height: 32px; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; color: #1d3557; }
.status.warn { color: #b35c00; }

// Code not found

Notice how the number of buckets stays small — at most $O(\log N)$ buckets of each size — while the estimated count closely tracks the true count. The merge rule is the heart of the algorithm: it sacrifices exact knowledge of when an event happened in exchange for a compact summary.

How much memory does sliding-window counting really require?

• Exact counting requires $\Omega(N)$ bits in the worst case — you must remember enough to distinguish $N$ different window boundaries.
• The exponential histogram (Datar et al., 2002) achieves a $(1+\varepsilon)$-approximation using only $O\!\left(\frac{1}{\varepsilon}\log^2 N\right)$ bits. For $\varepsilon = 0.1$ and $N = 10^6$ that is roughly $400$ counters — a factor of $2500$ compression.
• The lower bound matches (up to constants): any streaming algorithm that answers COUNT queries over a sliding window with relative error at most $\varepsilon$ needs $\Omega\!\left(\frac{1}{\varepsilon}\log^2 N\right)$ bits. The algorithm is essentially optimal.
• Merge invariant: the key to the space bound is that at most $\lceil 1/\varepsilon \rceil + 1$ buckets of each power-of-two size are kept. Merging two buckets of size $2^k$ into one of size $2^{k+1}$ is the only operation needed to restore this invariant after each new event.

The error arises only at the boundary bucket — the oldest bucket may straddle the window edge, so its contribution is counted with uncertainty at most half its size. This bounded error propagates to give the $(1+\varepsilon)$ guarantee.

This sits in the broader world of streaming algorithms and randomized approximation: problems where exact answers are too expensive, but provably accurate approximations are achievable in dramatically less space.

Any system that must answer "how many X happened recently?" without unlimited memory benefits from this idea:

• Infrastructure monitoring: counting errors, latency spikes, or request rates per minute on a live server — dashboards like Prometheus use sliding-window aggregations under the hood.
• Network traffic analysis: routers and intrusion-detection systems count packets per flow in real time; storing every packet timestamp is impossible at line speed.
• Database query optimization: database engines estimate how many rows satisfy a predicate in a recent time range to choose the fastest query plan.
• Click-stream analytics: ad-tech platforms count how many times a user has seen an ad in the last 24 hours before deciding whether to show it again.
• Anomaly detection: a spike in the approximate count signals a sudden burst of events and can trigger an alert, even when the exact count is unknowable without extra memory.

The exponential histogram is not the only tool in this space — Count-Min Sketch and other sketches tackle related problems — but it is the canonical answer to the sliding-window counting problem with a provable space lower bound.

The exponential histogram teaches a lesson that appears throughout algorithm design: you do not need to remember everything to know approximately how much happened. By grouping events into exponentially-growing buckets and enforcing a simple merge rule, the data structure compresses an endless stream into a handful of counters — and the error stays bounded by construction.

What makes this especially satisfying is the matching lower bound. The $O\!\left(\frac{1}{\varepsilon}\log^2 N\right)$ space is not just a clever trick — it is essentially the minimum possible. The algorithm and the lower bound together close the question of how hard sliding-window counting really is.

Next time a monitoring dashboard shows you a per-minute error rate, there is a good chance an exponential histogram — or something very much like it — is doing the counting behind the scenes, quietly discarding the past while keeping just enough to answer your question.