Sliding-Window Counting

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 = 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^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)$ 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.

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 $N$ positions.

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <button id="add0" type="button">{{btn_add0}}</button>
  <button id="add1" type="button">{{btn_add1}}</button>
  <button id="step" type="button">{{btn_step}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="window-row">
  <span class="label">{{lbl_window}}</span>
  <div id="bits" class="bits"></div>
</div>
<div class="bucket-row">
  <span class="label">{{lbl_buckets}}</span>
  <div id="buckets" class="buckets"></div>
</div>
<div class="counts">
  <span>{{lbl_exact}} <strong id="exact">0</strong></span>
  <span>{{lbl_dgim}} <strong id="dgim">0</strong></span>
  <span>{{lbl_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; }

// Code not found

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.

How tight is the DGIM solution?

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

"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 $N$ 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.

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)$-bit problem down to $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.