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 elements? Storing the window verbatim costs bits. DGIM does it in 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 bit patterns, which requires bits. Approximation is not a convenience here. It is the only way to beat . 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 , so 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 . Storing the exponent costs only bits.
Two invariants are maintained at all times:
- Bucket sizes are non-decreasing as you go back in time (newer buckets are the same size or smaller).
- There are at most two buckets of each size .
Because sizes are powers of two up to and there are of each, there are buckets, each needing bits — hence total.
The update rule
When a new bit arrives:
- Drop the oldest bucket if its timestamp is now more than positions old (it has left the window).
- If the new bit is 0, do nothing else.
- 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 appears, merge the two oldest of that size into one bucket of size (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):
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 . Stream (left = oldest), positions numbered as they arrive:
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:
| pos | bit | action | buckets (newest → oldest) |
|---|---|---|---|
| 1 | 1 | new size-1 | (1@1) |
| 2 | 0 | — | (1@1) |
| 3 | 1 | new size-1 | (1@3) (1@1) |
| 4 | 1 | new size-1 → three size-1 → merge two oldest | (1@4) (2@3) |
| 5 | 0 | — | (1@4) (2@3) |
| 6 | 1 | new size-1 | (1@6) (1@4) (2@3) |
| 7 | 1 | new size-1 → three size-1 → merge | (1@7) (2@6) (2@3) |
| 8 | 1 | new size-1 | (1@8) (1@7) (2@6) (2@3) |
Query at position 8, window = positions . 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:
The true count of 1s in positions 1–8 is . 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
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.
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 buckets per size (instead of 2) tightens the bound to 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 is essential to keep them bits; comparisons must account for the wraparound.
See also
- Streaming Algorithms & Sketches: the lesson this expands
- ADWIN: reuses the exponential-histogram bucket structure for drift detection