Introduction

Imagine a router logging every packet as a 1 and every idle slot as a 0. Every second it sees millions of bits. A traffic analyst wants to know: how many 1s arrived in the last N slots? That single question hides a fundamental tension.

The naive answer is to keep the last N bits in a circular buffer. If N=109N = 10^9, that is a gigabyte per counter — multiply by millions of routers and the numbers become absurd. So the question sharpens: can we answer approximately using only O(log⁡2N)O(\log^2 N) bits of memory?

The answer is yes, thanks to the DGIM algorithm, published in 2002 by Datar, Gionis, Indyk, and Motwani. It introduced the idea of exponential bucketing: rather than remembering individual bits, it keeps a small set of buckets whose sizes are powers of two, each stamped with the timestamp of its most recent 1. When a new 1 arrives, buckets merge like carries in binary addition, keeping the total count below O(log⁡N)O(\log N) buckets — and the error below 50%.

This article is about one of the cleanest results in streaming algorithms: solving a hard memory problem with a data structure that fits in a tweet.

Try It

The demo below simulates a bit-stream arriving one item at a time. Each incoming bit is either 0 or 1. Watch how DGIM builds and merges buckets as 1s arrive, and how the window evicts old buckets when their timestamps fall outside the last NN positions.

<p class="hint">Each incoming bit updates the DGIM bucket set. Buckets hold powers-of-two counts of 1s, stamped with the most-recent 1's timestamp. When the window slides, stale buckets expire.</p>
<div class="controls">
  <button id="add0" type="button">Add 0</button>
  <button id="add1" type="button">Add 1</button>
  <button id="step" type="button">Auto-step</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="window-row">
  <span class="label">Window:</span>
  <div id="bits" class="bits"></div>
</div>
<div class="bucket-row">
  <span class="label">Buckets:</span>
  <div id="buckets" class="buckets"></div>
</div>
<div class="counts">
  <span>Exact count: <strong id="exact">0</strong></span>
  <span>DGIM estimate: <strong id="dgim">0</strong></span>
  <span>Error: <strong id="err">0%</strong></span>
</div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .8rem; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.window-row, .bucket-row { display: flex; align-items: flex-start; gap: .5rem; margin-bottom: .5rem; }
.label { font-size: .78rem; font-weight: 700; color: #555; min-width: 68px; padding-top: 5px; }
.bits { display: flex; flex-wrap: wrap; gap: 3px; }
.bit { width: 22px; height: 22px; display: flex; align-items: center; justify-content: center;
       font: 700 12px ui-monospace, monospace; border-radius: 4px; }
.bit.b1 { background: #1d3557; color: #fff; }
.bit.b0 { background: #dde3ea; color: #555; }
.bit.new { outline: 2px solid #e63946; outline-offset: 1px; }
.buckets { display: flex; flex-wrap: wrap; gap: 4px; }
.bucket { display: flex; align-items: center; justify-content: center;
          border-radius: 6px; background: #4a7c59; color: #fff;
          font: 700 11px ui-monospace, monospace; padding: 3px 6px; }
.counts { display: flex; gap: 1.2rem; flex-wrap: wrap; margin: .6rem 0; font-size: .9rem; }
.status { font-size: .88rem; font-weight: 600; min-height: 1.3em; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// DGIM sliding-window 1-count: maintain exponential buckets, each
// N = window size (number of recent bits we care about)
const N = 32;
// Bucket = { size: power-of-two count of 1s it represents,
// ts: timestamp of the most recent 1 in the bucket }
let buckets = [];
// stream = circular buffer of last N bits (for exact reference only)
let stream = [];
// tick = global timestamp counter
let tick = 0;
// autoSeq = pre-generated bit sequence for auto-step mode
let autoSeq = [];
let autoIdx = 0;

// mergeBuckets: enforce DGIM invariant (at most 2 buckets of each size)
function mergeBuckets() {
  let changed = true;
  while (changed) {
    changed = false;
    // scan for 3 consecutive same-size buckets
    for (let i = 0; i < buckets.length - 2; i++) {
      if (buckets[i].size === buckets[i + 1].size && buckets[i].size === buckets[i + 2].size) {
        // merge the two oldest into a bucket of double size
        const merged = { size: buckets[i].size * 2, ts: buckets[i].ts };
        buckets.splice(i, 3, { size: buckets[i + 1].size, ts: buckets[i + 1].ts }, merged);
        changed = true;
        break;
      }
    }
    // general pass: merge any size that has more than 2 representatives
    for (let i = 0; i < buckets.length - 1; i++) {
      const sameCount = buckets.filter(b => b.size === buckets[i].size).length;
      if (sameCount > 2) {
        const idx = buckets.findIndex((b, j) => j > i && b.size === buckets[i].size);
        if (idx >= 0) {
          const merged = { size: buckets[i].size * 2, ts: Math.max(buckets[i].ts, buckets[idx].ts) };
          buckets.splice(idx, 1);
          buckets.splice(i, 1);
          buckets.push(merged);
          buckets.sort((a, b) => b.ts - a.ts);
          changed = true;
          break;
        }
      }
    }
  }
}

// expireBuckets: drop buckets whose most-recent-1 timestamp is outside window
function expireBuckets() {
  buckets = buckets.filter(b => b.ts > tick - N);
}

// dgimEstimate: sum all bucket sizes, halve the oldest one
function dgimEstimate() {
  if (buckets.length === 0) return 0;
  // oldest bucket may be only partially inside the window — count half
  const oldest = buckets[buckets.length - 1];
  let sum = 0;
  for (let i = 0; i < buckets.length - 1; i++) sum += buckets[i].size;
  return sum + Math.ceil(oldest.size / 2);
}

// exactCount: brute-force reference count from the circular buffer
function exactCount() {
  return stream.filter(b => b === 1).length;
}

function addBit(bit) {
  tick++;
  stream.push(bit);
  if (stream.length > N) stream.shift();
  if (bit === 1) {
    buckets.unshift({ size: 1, ts: tick });
    mergeBuckets();
  }
  expireBuckets();
  render();
}

function render() {
  // render the stream bits (newest = rightmost, highlighted in red outline)
  const bitsEl = document.getElementById('bits');
  bitsEl.innerHTML = '';
  stream.forEach((b, i) => {
    const d = document.createElement('div');
    d.className = 'bit b' + b + (i === stream.length - 1 ? ' new' : '');
    d.textContent = b;
    bitsEl.appendChild(d);
  });
  // render active buckets as colored chips
  const buckEl = document.getElementById('buckets');
  buckEl.innerHTML = '';
  buckets.forEach(bk => {
    const d = document.createElement('div');
    d.className = 'bucket';
    d.textContent = bk.size;
    d.title = i18nFmt('Bucket size %size% — most recent 1 at tick %ts%', { ts: bk.ts });
    buckEl.appendChild(d);
  });
  const exact = exactCount();
  const est = dgimEstimate();
  document.getElementById('exact').textContent = exact;
  document.getElementById('dgim').textContent = est;
  const errPct = exact === 0 ? 0 : Math.round(Math.abs(est - exact) / exact * 100);
  document.getElementById('err').textContent = errPct + '%';
  const msg = stream.length < N
    ? i18nFmt('Stream length %n% / %N% — window filling up.', { n: stream.length, N: N })
    : i18nFmt('Window full (%n% bits) · %b% active bucket(s).', { n: stream.length, b: buckets.length });
  document.getElementById('status').textContent = msg;
}

function stepAuto() {
  if (autoSeq.length === 0) {
    // generate a fresh 40-bit random sequence biased toward 1s
    for (let i = 0; i < 40; i++) autoSeq.push(Math.random() < 0.6 ? 1 : 0);
  }
  if (autoIdx < autoSeq.length) addBit(autoSeq[autoIdx++]);
}

document.getElementById('add0').addEventListener('click', () => addBit(0));
document.getElementById('add1').addEventListener('click', () => addBit(1));
document.getElementById('step').addEventListener('click', stepAuto);
document.getElementById('reset').addEventListener('click', () => {
  buckets = []; stream = []; tick = 0; autoSeq = []; autoIdx = 0;
  render();
});
render();
Result
Console

Notice that the exact count and the DGIM estimate stay close — the algorithm guarantees the estimate is within 50% of the true count. In practice the error is usually much smaller. The key insight: we never store the individual bits, only a logarithmic number of bucket summaries.

The Real Complexity

How tight is the DGIM solution?

  • Memory: at most 2log⁡2N2\log_2 N buckets exist at any time (at most 2 of each size 1,2,4,…,N/21, 2, 4, \ldots, N/2). Each bucket stores a size and a timestamp, costing O(log⁡N)O(\log N) bits each. Total: O(log⁡2N)O(\log^2 N) bits — a dramatic improvement over the O(N)O(N) bits of an exact buffer.
  • Update time: each incoming bit triggers at most O(log⁡N)O(\log N) merge operations (one cascade per doubling level), so each step runs in O(log⁡N)O(\log N) amortized time.
  • Error guarantee: the DGIM estimate c^\hat{c} satisfies (1−ε)⋅c≤c^≤(1+ε)⋅c(1-\varepsilon) \cdot c \le \hat{c} \le (1+\varepsilon) \cdot c where ε≤1/2\varepsilon \le 1/2. With a small constant-factor increase in memory, ε\varepsilon can be driven down to any fixed δ>0\delta > 0.
  • Lower bound: a communication-complexity argument shows that any exact algorithm for sliding-window counting requires Ω(N)\Omega(N) bits of memory, confirming that approximation is necessary — not a shortcut.

The DGIM algorithm sits at the intersection of streaming algorithms and classic data-stream theory. It shows that the right approximation guarantee, combined with the right structure, can turn an impossible exact problem into a practical one. See also space-efficient data structures for a complementary trick in a different setting.

Where It Matters

"How many events happened recently?" is one of the most universal questions in real-time systems, and DGIM-style counting is its practical answer:

  • Network intrusion detection: a router counts SYN packets in the last NN slots. A sudden spike signals a flood attack — even an approximate count is enough to trigger an alert.
  • Click-stream analytics: a web platform estimates how many users clicked a banner in the last hour, without storing every click in a hot database.
  • Fraud detection: a payment processor counts suspicious transactions per card in a rolling window. Memory is precious on embedded hardware.
  • Sensor networks: IoT devices with kilobytes of RAM aggregate readings over time windows without ever transmitting or storing raw histories.
  • Database query engines: approximate COUNT queries over sliding time windows power dashboards that must respond in milliseconds.

The elegance is that a few dozen bytes of bucket state can represent millions of recent events — a concrete win for the theory of data compression applied to live computation.

Conclusion

The DGIM algorithm is a small masterpiece of algorithmic thinking: it trades exactness for a guaranteed approximation and, in doing so, compresses an O(N)O(N)-bit problem down to O(log⁡2N)O(\log^2 N) bits. The lower bound closes the loop — you cannot do better without accepting more error.

Next time a dashboard shows you "approximately 1.2 million events in the last hour," remember: that number likely came from a handful of exponentially-sized buckets merging and expiring in real time, using less memory than a single JPEG thumbnail. The gap between what a stream contains and what an algorithm needs to remember is where streaming theory lives — and DGIM showed that gap can be enormous.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/sliding-window-counting/Content licensed under CC BY-NC 4.0.