FA-73310 / Probabilistic sketches / Member archive

DGIM sliding-window bit counting: merge does not cascade · case 05

After a merge, three buckets of the doubled size can coexist.

Member previewVariant 5 · 3 implementations · 7 checks per implementation

Case contract

Input {W, bits, queries}; timestamps start at 1. Buckets are [size, timestamp of most recent 1], newest first. Before processing time t, buckets with timestamp <= t - W expire. A 1 bit adds [1, t]; while more than two buckets share a size, the two oldest of that size merge into one of double size keeping the more recent timestamp, cascading upward. At a query time the estimate is the total size minus floor(oldest size / 2). Return [[t, estimate] per query, final buckets].

Why this case matters

Exponential-histogram counters approximate "events in the last W ticks" in logarithmic memory for streaming monitors; merge and expiry rules determine the error bound.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
stream 0 W=10	`[[[15, 6], [27, 8], [30, 7]], [[1, 29], [1, 27], [2, 26], [2, 23], [2, 21]]]`	`[[[15, 5], [27, 7], [30, 8]], [[1, 29], [1, 27], [2, 26], [2, 23], [4, 21]]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.