FA-73337 / Probabilistic sketches / Member archive
Top-k tracking over a Count-Min sketch: candidate scored before its own update · case 02
Each key is scored without its current occurrence, so newcomers can never beat equal incumbents.
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 |
|---|---|---|---|
| stream 0 w=8 k=2 | [[2, 15], [4, 7]] | [[2, 19], [4, 9]] | 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 ↗