DGIM: Counting Ones in a Sliding WindowOpen in Colab

DGIM: Counting Ones in a Sliding Window

The DGIM algorithm (Datar, Gionis, Indyk, Motwani, 2002) answers a deceptively simple question on a binary stream: how many 1s occurred in the last NN elements? Storing the window verbatim costs NN bits. DGIM does it in O(log⁡2N)O(\log^2 N) bits with a guaranteed error of at most 50% — the canonical example of trading exactness for sublinear memory over a sliding window.

Why exact counting is impossible in sublinear space

If you must answer exactly for every possible window content, you need to distinguish all 2N2^N bit patterns, which requires NN bits. Approximation is not a convenience here. It is the only way to beat O(N)O(N). DGIM commits to a bounded relative error and spends its memory on a clever summary.

Buckets

DGIM summarises the window with buckets. Each bucket covers a contiguous range of stream positions and records two things:

  • Timestamp of its most recent 1, stored modulo NN, so O(log⁡N)O(\log N) bits. This lets DGIM tell when a bucket has slid out of the window.
  • Size = the number of 1s in the bucket, which is always a power of two 2j2^j. Storing the exponent jj costs only O(log⁡log⁡N)O(\log\log N) bits.

Two invariants are maintained at all times:

  1. Bucket sizes are non-decreasing as you go back in time (newer buckets are the same size or smaller).
  2. There are at most two buckets of each size 2j2^j.

Because sizes are powers of two up to NN and there are ≤2\le 2 of each, there are O(log⁡N)O(\log N) buckets, each needing O(log⁡N)O(\log N) bits — hence O(log⁡2N)O(\log^2 N) total.

The update rule

When a new bit arrives:

  1. Drop the oldest bucket if its timestamp is now more than NN positions old (it has left the window).
  2. If the new bit is 0, do nothing else.
  3. If the new bit is 1, create a new size-1 bucket for it (timestamp = current time). Then cascade merges: whenever a third bucket of size 2j2^j appears, merge the two oldest of that size into one bucket of size 2j+12^{j+1} (timestamp = the newer of the two). A merge can trigger another merge one level up, and so on.

Answering a query

To estimate the number of 1s in the window, sum the sizes of all buckets fully inside the window, then add half the size of the oldest bucket (the one that only partially overlaps the window boundary):

c^  =  (∑fully-inside bucketssize)  +  12 size(oldest partial bucket).\widehat{c} \;=\; \Big(\textstyle\sum_{\text{fully-inside buckets}} \text{size}\Big) \;+\; \tfrac{1}{2}\,\text{size}(\text{oldest partial bucket}).

That single halved bucket is the only source of error. Since we know the true count of the oldest bucket is between half and its full size, the estimate is off by at most half of it, giving the ≤ 50% relative error bound (and typically far less, because the oldest bucket is a small fraction of the total).

Worked trace

Window N=8N = 8. Stream (left = oldest), positions numbered as they arrive:

Code
position:  1 2 3 4 5 6 7 8
bit:       1 0 1 1 0 1 1 1

Process bit by bit, listing buckets as (size @ most-recent-1-timestamp), newest first:

posbitactionbuckets (newest → oldest)
11new size-1(1@1)
20—(1@1)
31new size-1(1@3) (1@1)
41new size-1 → three size-1 → merge two oldest(1@4) (2@3)
50—(1@4) (2@3)
61new size-1(1@6) (1@4) (2@3)
71new size-1 → three size-1 → merge(1@7) (2@6) (2@3)
81new size-1(1@8) (1@7) (2@6) (2@3)

Query at position 8, window = positions [1,8][1,8]. Every bucket's most-recent-1 timestamp is inside the window, so the oldest bucket (2@3) is the partial one. Sum the rest fully and add half the oldest:

c^=1⏟@8+1⏟@7+2⏟@6+12⋅2⏟@3=5.\widehat c = \underbrace{1}_{@8} + \underbrace{1}_{@7} + \underbrace{2}_{@6} + \tfrac{1}{2}\cdot \underbrace{2}_{@3} = 5.

The true count of 1s in positions 1–8 is 1+1+1+1+1+1=61+1+1+1+1+1 = 6. The estimate 5 is within the 50% guarantee (here ~17% low). As the window slides past position 3, the (2@3) bucket is dropped and the estimate tightens.

Watch it run

The worked stream above, bit by bit, with the merge cascade and the half-counted oldest bucket visible at every step:

DGIM — exponential buckets over a sliding window

1/11

A binary stream and a window of the last N = 8 bits. The question is how many 1s are in the window. Storing the window costs 8 bits and answers exactly; DGIM answers approximately in O(log² N) bits, and the approximation is not a convenience — distinguishing all 2^N window contents *requires* N bits, so sublinear memory forces it.

python
1def update(buckets, bit, t, N):
2 # drop whatever has slid out of the window
3 buckets = [b for b in buckets
4 if t - b.ts < N]
5 if bit == 0:
6 return buckets
7 buckets.insert(0, Bucket(size=1, ts=t))
8 # cascade: never 3 buckets of one size
9 size = 1
10 while count(buckets, size) > 2:
11 a, b = two_oldest(buckets, size)
12 buckets.remove(a); buckets.remove(b)
13 merged = Bucket(2 * size, ts=newer(a, b))
14 insert_sorted(buckets, merged)
15 size *= 2
16 return buckets
17
18def estimate(buckets):
19 # all but the oldest count in full
20 return (sum(b.size for b in buckets[:-1])
21 + buckets[-1].size / 2)
state
stream — window is the last 8 positions
11
buckets (newest → oldest)
empty

Each bucket stores only the timestamp of its most recent 1 (O(log N) bits) and its size as a power of two (O(log log N) bits). It never stores which positions held 1s.

Bit by bit through the worked stream above, with the merge cascade that keeps at most two buckets of each size. Watch what DGIM never stores: not which positions held 1s, only a timestamp and a power-of-two size per bucket. The final step runs the stream out and queries at every position, so the ≤50% error bound stops being a claim and becomes a measured envelope — the real error stays far below it.

What to notice as you step:

  • Zeros cost nothing. DGIM only ever records 1s; a 0 changes no bucket and consumes no memory.
  • A merge loses information deliberately. Combining two size-1 buckets into a size-2 discards which positions held the 1s, keeping only the newer timestamp. That erasure is the whole memory saving.
  • The error lives entirely in one bucket. Every bucket but the oldest counts in full and is exact; only the oldest is halved, so it is the sole source of error and the sole reason for the ≤50% bound.
  • The estimate is biased low, always, and the final step queries at every position to show the real error staying far inside the guarantee.

Gotchas & extensions

  • Error is one-sided in structure, not sign. The halving of the oldest bucket can make the estimate high or low, but always within 50%. Keeping rr buckets per size (instead of 2) tightens the bound to O(1/r)O(1/r) at higher memory cost.
  • Sums, not just counts. DGIM generalises to sliding-window sums of small integers, and the same exponential histogram idea underlies streaming variance and, notably, ADWIN's change detector.
  • Timestamps wrap. Storing timestamps mod NN is essential to keep them O(log⁡N)O(\log N) bits; comparisons must account for the wraparound.

See also

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
DGIM: Counting Ones in a Sliding …ADWIN: Adaptive Windowing…Streaming Algorithms & Sk…