FA-73335 / Probabilistic sketches / Member archive

Top-k tracking over a Count-Min sketch: tie among minima evicts the newest entry · case 05

Which minimum-score key survives depends on insertion history instead of the stated tie-break.

Member previewVariant 5 · 3 implementations · 10 checks per implementation

Case contract

Input {w, k, stream of [key, count]}. A three-row Count-Min sketch (fixed hash family) is updated first; the key's estimate is then the minimum of its cells. A tracked key's score is refreshed to the new estimate; an untracked key enters while fewer than k are tracked; otherwise it replaces the victim with the smallest score (ties: smallest key) only if its estimate is strictly larger. Return [key, score] rows sorted by score descending then key.

Why this case matters

Streaming top-k dashboards pair a frequency sketch with a small candidate table; stale scores or loose replacement rules make the reported leaders wrong.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
tie among minima eviction	`[[7, 10], [4, 3]]`	`[[7, 10], [9, 3]]`	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.