FA-73315 / Probabilistic sketches / Member archive

DGIM sliding-window bit counting: bucket at the window edge not expired · case 05

A 1 that is exactly W ticks old is still counted.

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 1 W=8	`[[[12, 4], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]`	`[[[12, 2], [22, 7], [25, 5]], [[1, 24], [1, 22], [2, 20], [2, 18]]]`	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.