Introduction

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 NN 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)O(N) space — and NN 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+ε)(1+\varepsilon) factor of the true count using only O ⁣(1εlog⁡2N)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.

Try It

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.

<!-- Exponential histogram demo — approximate sliding-window event count in sublinear space -->
<p class="hint">Each click adds one event to the stream. Buckets of equal size merge when there are too many, keeping memory logarithmic. The estimated count approximates the true count within the window.</p>
<div class="controls">
  <button id="btn-add" type="button">Add event</button>
  <button id="btn-stream" type="button">Auto-stream</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <label class="param-label">Window N:
    <input id="inp-window" type="number" min="8" max="128" value="32" />
  </label>
  <label class="param-label">ε:
    <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">True count</span><span id="true-count" class="stat-val">0</span></span>
  <span class="stat-box"><span class="stat-label">Estimated</span><span id="est-count" class="stat-val">0</span></span>
  <span class="stat-box"><span class="stat-label">Error</span><span id="error-pct" class="stat-val">—</span></span>
  <span class="stat-box"><span class="stat-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>

/* Styles for the exponential histogram demo */
* { 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; }

/* Exponential histogram — approximate sliding-window count in O((1/eps) log^2 N) space */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Color palette — one hue per power-of-two bucket size */
const COLORS = ['#264653','#2a9d8f','#e9c46a','#f4a261','#e76f51','#8338ec','#3a86ff'];

/* Algorithm state */
let N = 32;
let K = 4; /* max buckets per size = ceil(1/eps); K=4 for eps=0.25 */
let stream = []; /* all event timestamps (for true-count verification) */
let buckets = []; /* exponential histogram: list of {size, end} from oldest to newest */
let tick = 0;
let streamTimer = null;

/* Return the count of events a bucket represents */
function bucketSize(b) { return b.size; }

/* Add one event at the current tick */
function addEvent() {
  tick++;
  stream.push(tick);
  /* newest event becomes a size-1 bucket */
  buckets.push({ size: 1, end: tick });
  mergeBuckets();
  expire();
  render();
}

/* Restore the invariant — at most K buckets of each size */
function mergeBuckets() {
  let changed = true;
  while (changed) {
    changed = false;
    /* group bucket indices by their size */
    const sizes = {};
    buckets.forEach((b, i) => { (sizes[b.size] = sizes[b.size] || []).push(i); });
    for (const sz in sizes) {
      if (sizes[sz].length > K) {
        /* merge the two oldest (leftmost) buckets of this size */
        const [i0, i1] = sizes[sz].slice(0, 2);
        const merged = { size: buckets[i0].size * 2, end: buckets[i1].end };
        buckets.splice(i0, 2, merged);
        changed = true;
        break;
      }
    }
  }
}

/* Discard buckets whose newest event is outside the window */
function expire() {
  const cutoff = tick - N;
  buckets = buckets.filter(b => b.end > cutoff);
}

/* Approximate count: sum all buckets, halve the boundary bucket */
function estimate() {
  if (buckets.length === 0) return 0;
  let sum = 0;
  const cutoff = tick - N;
  for (let i = 0; i < buckets.length; i++) {
    const b = buckets[i];
    if (i === 0) {
      /* oldest bucket may straddle window edge — count half its size */
      sum += Math.ceil(b.size / 2);
    } else {
      sum += b.size;
    }
  }
  return sum;
}

/* Exact count by scanning the full event list (for verification only) */
function trueCount() {
  const cutoff = tick - N;
  return stream.filter(t => t > cutoff).length;
}

/* Draw the event timeline on the canvas */
function drawTimeline() {
  const canvas = document.getElementById('timeline');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  const cutoff = tick - N;
  const maxTick = tick || 1;
  const minTick = Math.max(0, tick - N * 1.5);
  const range = maxTick - minTick || 1;
  /* shade the active window region */
  const wx = ((cutoff - minTick) / range) * W;
  ctx.fillStyle = 'rgba(29,53,87,0.08)';
  ctx.fillRect(Math.max(0, wx), 0, W - Math.max(0, wx), H);
  /* draw a tick mark for each event */
  ctx.fillStyle = '#2a9d8f';
  stream.forEach(t => {
    const x = ((t - minTick) / range) * W;
    ctx.fillRect(x - 1, 8, 3, H - 16);
  });
  /* label the window region */
  ctx.fillStyle = '#1d3557';
  ctx.font = '10px system-ui';
  ctx.fillText('window', Math.max(4, wx + 4), H - 4);
}

/* Update all UI elements after each event */
function render() {
  const tc = trueCount();
  const est = estimate();
  document.getElementById('true-count').textContent = tc;
  document.getElementById('est-count').textContent = est;
  const errEl = document.getElementById('error-pct');
  if (tc > 0) {
    const pct = Math.abs(est - tc) / tc * 100;
    errEl.textContent = pct.toFixed(1) + '%';
    errEl.style.color = pct > 25 ? '#c92f3c' : '#0a7d33';
  } else {
    errEl.textContent = '—';
    errEl.style.color = '';
  }
  document.getElementById('bucket-count').textContent = buckets.length;
  /* render bucket boxes proportional to their size */
  const vis = document.getElementById('bucket-vis');
  vis.innerHTML = '';
  const maxSz = buckets.length ? Math.max(...buckets.map(b => b.size)) : 1;
  buckets.forEach((b, i) => {
    const div = document.createElement('div');
    div.className = 'bucket';
    const w = Math.max(22, Math.round(20 + (b.size / maxSz) * 60));
    div.style.width = w + 'px';
    div.style.background = COLORS[Math.min(Math.floor(Math.log2(b.size)), COLORS.length - 1)];
    div.title = i18nFmt('size=%size%, last event at t=%end%', { size: b.size, end: b.end });
    div.textContent = b.size;
    vis.appendChild(div);
  });
  drawTimeline();
  /* update the status line */
  const statusEl = document.getElementById('status');
  if (tick === 0) {
    statusEl.textContent = 'Add events or press Auto-stream to begin.';
    statusEl.className = 'status';
  } else {
    statusEl.textContent = i18nFmt('t=%tick% · %buckets% bucket(s) stored', { tick: tick, buckets: buckets.length });
    statusEl.className = 'status';
  }
}

/* Wire up button event listeners */
document.getElementById('btn-add').addEventListener('click', addEvent);

document.getElementById('btn-stream').addEventListener('click', function () {
  if (streamTimer) {
    clearInterval(streamTimer);
    streamTimer = null;
    this.textContent = 'Auto-stream';
  } else {
    this.textContent = 'Stop';
    streamTimer = setInterval(addEvent, 200);
  }
});

document.getElementById('btn-reset').addEventListener('click', function () {
  if (streamTimer) { clearInterval(streamTimer); streamTimer = null; }
  document.getElementById('btn-stream').textContent = 'Auto-stream';
  tick = 0; stream = []; buckets = [];
  N = parseInt(document.getElementById('inp-window').value) || 32;
  K = Math.max(2, Math.round(1 / (parseFloat(document.getElementById('inp-eps').value) || 0.25)));
  render();
});

document.getElementById('inp-window').addEventListener('change', function () {
  N = parseInt(this.value) || 32;
});
document.getElementById('inp-eps').addEventListener('change', function () {
  K = Math.max(2, Math.round(1 / (parseFloat(this.value) || 0.25)));
});

/* Initialize with values from the input fields */
N = parseInt(document.getElementById('inp-window').value) || 32;
K = Math.max(2, Math.round(1 / (parseFloat(document.getElementById('inp-eps').value) || 0.25)));
render();
Result
Console

Notice how the number of buckets stays small — at most O(log⁡N)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.

The Real Complexity

How much memory does sliding-window counting really require?

  • Exact counting requires Ω(N)\Omega(N) bits in the worst case — you must remember enough to distinguish NN different window boundaries.
  • The exponential histogram (Datar et al., 2002) achieves a (1+ε)(1+\varepsilon)-approximation using only O ⁣(1εlog⁡2N)O\!\left(\frac{1}{\varepsilon}\log^2 N\right) bits. For ε=0.1\varepsilon = 0.1 and N=106N = 10^6 that is roughly 400400 counters — a factor of 25002500 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 Ω ⁣(1εlog⁡2N)\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 ⌈1/ε⌉+1\lceil 1/\varepsilon \rceil + 1 buckets of each power-of-two size are kept. Merging two buckets of size 2k2^k into one of size 2k+12^{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+ε)(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.

Where It Matters

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.

Conclusion

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 ⁣(1εlog⁡2N)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/exponential-histograms/Content licensed under CC BY-NC 4.0.