FA-73317 / Probabilistic sketches / Member archive

DGIM sliding-window bit counting: estimate halves the newest bucket · case 02

The uncertainty correction is applied to the fully-inside newest bucket instead of the straddling oldest one.

Member previewVariant 2 · 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, 4], [27, 5], [30, 8]], [[1, 30], [1, 29], [2, 28], [4, 22]]]`	`[[[15, 3], [27, 4], [30, 6]], [[1, 30], [1, 29], [2, 28], [4, 22]]]`	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.