FA-73110 / Probabilistic sketches / Member archive

Weighted Misra-Gries frequent items: discarded mass omits the newcomer · case 05

The reported error bound is smaller than the mass actually discarded.

Member previewVariant 5 · 3 implementations · 7 checks per implementation

Case contract

Input {k, stream} of [item, positive weight]. Keep at most k counters. A tracked item adds its weight; an untracked item takes a free counter. Otherwise dec = min(smallest counter, weight) is subtracted from every counter and from the incoming weight, counters reaching 0 are dropped, and a positive remainder is inserted. removed accumulates dec*(k+1), the discarded mass. Return [sorted [item, count] pairs, removed].

Why this case matters

Heavy-hitter detection over weighted traffic (bytes per flow, spend per account) relies on the deterministic Misra-Gries error bound removed/(k+1).

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
weighted stream 0 k=2	`[[["d", 1], ["e", 7]], 28]`	`[[["d", 1], ["e", 7]], 42]`	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.