FA-73332 / Probabilistic sketches / Member archive
Top-k tracking over a Count-Min sketch: tie among minima evicts the newest entry · case 02
Which minimum-score key survives depends on insertion history instead of the stated tie-break.
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 fixtureThis sample comes from the broken implementation of a controlled reproducer.
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| tie among minima eviction | [[7, 7], [4, 3]] | [[7, 7], [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.
Sign in to the archive ↗