FA-73142 / Probabilistic sketches / Member archive
Space-Saving heavy hitters: equal counts listed in insertion order · case 02
Top-k reports with tied counts are ordered inconsistently between runs with different arrival orders.
Case contract
Input {k, stream, phi=[num, den]}. Keep k entries [count, error, last-touch tick]. A hit increments count and refreshes the tick. A miss with free space inserts [1, 0, tick]. Otherwise evict the entry with the smallest count, ties broken by the oldest tick, and insert the newcomer with count = victim count + 1 and error = victim count. Return [rows sorted by count descending then item, sorted items whose guaranteed count (count - error) exceeds phi * stream length].
Why this case matters
Top-k dashboards and abuse detectors use Space-Saving because its per-item error bound lets them separate guaranteed heavy hitters from possible ones.
One recorded failure
Sample boundary fixtureThis sample comes from the broken implementation of a controlled reproducer.
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 2 k=3 | [[["a", 6, 0], ["c", 5, 2], ["b", 5, 3]], ["a"]] | [[["a", 6, 0], ["b", 5, 3], ["c", 5, 2]], ["a"]] | 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 ↗