FA-73094 / Probabilistic sketches / Member archive

Weighted Misra-Gries frequent items: newcomer inserted with its full weight · case 04

Counters exceed the true frequency and the error guarantee no longer holds.

Member previewVariant 4 · 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	`[[["b", 4], ["d", 1], ["e", 3]], 45]`	`[[["b", 3]], 39]`	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.