FA-73323 / Probabilistic sketches / Member archive
Top-k tracking over a Count-Min sketch: tracked scores never refreshed · case 03
An established leader keeps its entry score and is evicted by newer, smaller keys.
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 1 w=6 k=3 | [[4, 11], [5, 8], [6, 7]] | [[4, 14], [5, 12], [6, 11]] | 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 ↗