FA-73136 / Probabilistic sketches / Open access
Space-Saving heavy hitters: guarantee ignores the error bound · case 01
Items whose count is mostly inherited error are reported as guaranteed heavy hitters.
ROOT CAUSE
The guarantee test uses the raw count instead of count - error.
VERIFIED REPAIR
Compare count - error strictly against phi * N.
Unsuccessful approach: Making the comparison inclusive admits items exactly at the threshold.
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.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
S = {}
tick = 0
for item in x['stream']:
tick += 1
if item in S:
S[item][0] += 1
S[item][2] = tick
elif len(S) < k:
S[item] = [1, 0, tick]
else:
victim = min(S, key=lambda key: (S[key][0], S[key][2]))
cnt = S.pop(victim)[0]
S[item] = [cnt + 1, cnt, tick]
Ntot = len(x['stream'])
num, den = x['phi']
rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))
guaranteed = sorted(key for key, v in S.items() if v[0] * den > num * Ntot)
return [rows, guaranteed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},
[[['a', 9, 3], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},
[[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},
[[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},
[[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},
[[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},
[[['a', 10, 4], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},
[[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},
[[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},
[[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},
[[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'a',
'b',
'b',
'b',
'a',
'e',
'a',
'a',
'a',
'b',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['d',
'b',
'a',
'a',
'a',
'e',
'c',
'a',
'f',
'c',
'a',
'e',
'b',
'a',
'a',
'a',
'a']},
[[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'd',
'b',
'c',
'c',
'c',
'a',
'd',
'c',
'b',
'd',
'b',
'a',
'b']},
[[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'a',
'c',
'c',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'c',
'd',
'a']},
[[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},
[[['c', 3, 2], ['a', 2, 0]], ['a']]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},
[[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['d',
'a',
'c',
'a',
'b',
'a',
'b',
'a',
'e',
'a',
'a',
'a',
'd',
'c',
'b',
'a',
'b',
'a']},
[[['a', 9, 7], ['b', 9, 7]], []]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'f',
'f',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'a',
'a',
'b']},
[[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'c',
'c',
'e',
'a',
'f',
'c',
'c',
'e',
'd',
'f',
'b',
'a',
'a',
'c',
'b',
'b']},
[[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['e',
'a',
'a',
'a',
'a',
'b',
'a',
'd',
'e',
'a',
'd',
'a',
'g',
'a',
'c',
'g',
'c',
'b']},
[[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},
[[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'a',
'a',
'b',
'a',
'a',
'c',
'a',
'e',
'a',
'a',
'a',
'a',
'a',
'a',
'd',
'c']},
[[['a', 13, 0], ['c', 6, 5]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'b',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'b',
'a',
'f',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'a',
'a',
'c',
'f',
'f',
'a',
'a',
'a',
'b',
'b',
'b',
'b',
'a',
'd',
'a',
'a']},
[[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b',
'c',
'a',
'b',
'a',
'b',
'a',
'b',
'b',
'a',
'a',
'c',
'd',
'f',
'a',
'd',
'a',
'a',
'g']},
[[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},
[[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 0 k=2 | [[['a', 9, 3], ['b', 6, 4]], ['a', 'b']] | [[['a', 9, 3], ['b', 6, 4]], ['a']] | Failed |
| skewed stream 1 k=3 | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a', 'b']] | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | Failed |
| skewed stream 2 k=3 | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a', 'c']] | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | Failed |
| skewed stream 3 k=4 | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | Passed |
| tie eviction by age | [[['c', 3, 2], ['d', 3, 2]], ['c', 'd']] | [[['c', 3, 2], ['d', 3, 2]], []] | Failed |
| boundary threshold | [[['c', 4, 3], ['b', 3, 0]], ['c']] | [[['c', 4, 3], ['b', 3, 0]], []] | Failed |
| refresh on hit | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Passed |
| equal counts different recency | [[['q', 3, 2], ['r', 3, 2]], ['q', 'r']] | [[['q', 3, 2], ['r', 3, 2]], []] | Failed |
| no eviction | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Passed |
SHA-256 / d7eb8083e6f22115386784c73fb9dc9509bd1075c30525e034e12177fab50858
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
S = {}
tick = 0
for item in x['stream']:
tick += 1
if item in S:
S[item][0] += 1
S[item][2] = tick
elif len(S) < k:
S[item] = [1, 0, tick]
else:
victim = min(S, key=lambda key: (S[key][0], S[key][2]))
cnt = S.pop(victim)[0]
S[item] = [cnt + 1, cnt, tick]
Ntot = len(x['stream'])
num, den = x['phi']
rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))
guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den >= num * Ntot)
return [rows, guaranteed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},
[[['a', 9, 3], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},
[[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},
[[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},
[[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},
[[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},
[[['a', 10, 4], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},
[[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},
[[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},
[[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},
[[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'a',
'b',
'b',
'b',
'a',
'e',
'a',
'a',
'a',
'b',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['d',
'b',
'a',
'a',
'a',
'e',
'c',
'a',
'f',
'c',
'a',
'e',
'b',
'a',
'a',
'a',
'a']},
[[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'd',
'b',
'c',
'c',
'c',
'a',
'd',
'c',
'b',
'd',
'b',
'a',
'b']},
[[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'a',
'c',
'c',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'c',
'd',
'a']},
[[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},
[[['c', 3, 2], ['a', 2, 0]], ['a']]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},
[[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['d',
'a',
'c',
'a',
'b',
'a',
'b',
'a',
'e',
'a',
'a',
'a',
'd',
'c',
'b',
'a',
'b',
'a']},
[[['a', 9, 7], ['b', 9, 7]], []]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'f',
'f',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'a',
'a',
'b']},
[[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'c',
'c',
'e',
'a',
'f',
'c',
'c',
'e',
'd',
'f',
'b',
'a',
'a',
'c',
'b',
'b']},
[[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['e',
'a',
'a',
'a',
'a',
'b',
'a',
'd',
'e',
'a',
'd',
'a',
'g',
'a',
'c',
'g',
'c',
'b']},
[[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},
[[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'a',
'a',
'b',
'a',
'a',
'c',
'a',
'e',
'a',
'a',
'a',
'a',
'a',
'a',
'd',
'c']},
[[['a', 13, 0], ['c', 6, 5]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'b',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'b',
'a',
'f',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'a',
'a',
'c',
'f',
'f',
'a',
'a',
'a',
'b',
'b',
'b',
'b',
'a',
'd',
'a',
'a']},
[[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b',
'c',
'a',
'b',
'a',
'b',
'a',
'b',
'b',
'a',
'a',
'c',
'd',
'f',
'a',
'd',
'a',
'a',
'g']},
[[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},
[[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 0 k=2 | [[['a', 9, 3], ['b', 6, 4]], ['a']] | [[['a', 9, 3], ['b', 6, 4]], ['a']] | Passed |
| skewed stream 1 k=3 | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | Passed |
| skewed stream 2 k=3 | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | Passed |
| skewed stream 3 k=4 | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | Passed |
| tie eviction by age | [[['c', 3, 2], ['d', 3, 2]], []] | [[['c', 3, 2], ['d', 3, 2]], []] | Passed |
| boundary threshold | [[['c', 4, 3], ['b', 3, 0]], ['b']] | [[['c', 4, 3], ['b', 3, 0]], []] | Failed |
| refresh on hit | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Passed |
| equal counts different recency | [[['q', 3, 2], ['r', 3, 2]], []] | [[['q', 3, 2], ['r', 3, 2]], []] | Passed |
| no eviction | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r', 's']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Failed |
SHA-256 / c6c64e9575d00c237c2f5088cdbbd005a845e1315439548c6ac90fa4bc8e52f8
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
S = {}
tick = 0
for item in x['stream']:
tick += 1
if item in S:
S[item][0] += 1
S[item][2] = tick
elif len(S) < k:
S[item] = [1, 0, tick]
else:
victim = min(S, key=lambda key: (S[key][0], S[key][2]))
cnt = S.pop(victim)[0]
S[item] = [cnt + 1, cnt, tick]
Ntot = len(x['stream'])
num, den = x['phi']
rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))
guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)
return [rows, guaranteed]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},
[[['a', 9, 3], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},
[[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},
[[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},
[[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},
[[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},
[[['a', 10, 4], ['b', 6, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},
[[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},
[[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},
[[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},
[[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'a',
'b',
'b',
'b',
'a',
'e',
'a',
'a',
'a',
'b',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 4]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['d',
'b',
'a',
'a',
'a',
'e',
'c',
'a',
'f',
'c',
'a',
'e',
'b',
'a',
'a',
'a',
'a']},
[[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'd',
'b',
'c',
'c',
'c',
'a',
'd',
'c',
'b',
'd',
'b',
'a',
'b']},
[[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['a',
'a',
'a',
'b',
'a',
'c',
'c',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'c',
'd',
'a']},
[[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},
[[['c', 3, 2], ['a', 2, 0]], ['a']]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},
[[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['d',
'a',
'c',
'a',
'b',
'a',
'b',
'a',
'e',
'a',
'a',
'a',
'd',
'c',
'b',
'a',
'b',
'a']},
[[['a', 9, 7], ['b', 9, 7]], []]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'f',
'f',
'c',
'c',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'a',
'a',
'b']},
[[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'c',
'c',
'e',
'a',
'f',
'c',
'c',
'e',
'd',
'f',
'b',
'a',
'a',
'c',
'b',
'b']},
[[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['e',
'a',
'a',
'a',
'a',
'b',
'a',
'd',
'e',
'a',
'd',
'a',
'g',
'a',
'c',
'g',
'c',
'b']},
[[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},
[[['c', 3, 2], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},
[[['r', 3, 2], ['p', 2, 0]], ['p']]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},
[[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],
[['skewed stream 0 k=2',
{'k': 2,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'a',
'a',
'b',
'a',
'a',
'c',
'a',
'e',
'a',
'a',
'a',
'a',
'a',
'a',
'd',
'c']},
[[['a', 13, 0], ['c', 6, 5]], ['a']]],
['skewed stream 1 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'a',
'b',
'b',
'a',
'a',
'b',
'b',
'a',
'a',
'c',
'a',
'b',
'a',
'f',
'a',
'a',
'a',
'a']},
[[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],
['skewed stream 2 k=3',
{'k': 3,
'phi': [1, 4],
'stream': ['a',
'b',
'a',
'a',
'a',
'c',
'f',
'f',
'a',
'a',
'a',
'b',
'b',
'b',
'b',
'a',
'd',
'a',
'a']},
[[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],
['skewed stream 3 k=4',
{'k': 4,
'phi': [1, 4],
'stream': ['b',
'c',
'a',
'b',
'a',
'b',
'a',
'b',
'b',
'a',
'a',
'c',
'd',
'f',
'a',
'd',
'a',
'a',
'g']},
[[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],
['tie eviction by age',
{'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},
[[['b', 4, 3], ['d', 3, 2]], []]],
['boundary threshold',
{'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},
[[['c', 4, 3], ['b', 3, 0]], []]],
['refresh on hit',
{'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},
[[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],
['equal counts different recency',
{'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},
[[['q', 3, 2], ['r', 3, 2]], []]],
['no eviction',
{'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},
[[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| skewed stream 0 k=2 | [[['a', 9, 3], ['b', 6, 4]], ['a']] | [[['a', 9, 3], ['b', 6, 4]], ['a']] | Passed |
| skewed stream 1 k=3 | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']] | Passed |
| skewed stream 2 k=3 | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']] | Passed |
| skewed stream 3 k=4 | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']] | Passed |
| tie eviction by age | [[['c', 3, 2], ['d', 3, 2]], []] | [[['c', 3, 2], ['d', 3, 2]], []] | Passed |
| boundary threshold | [[['c', 4, 3], ['b', 3, 0]], []] | [[['c', 4, 3], ['b', 3, 0]], []] | Passed |
| refresh on hit | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']] | Passed |
| equal counts different recency | [[['q', 3, 2], ['r', 3, 2]], []] | [[['q', 3, 2], ['r', 3, 2]], []] | Passed |
| no eviction | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']] | Passed |
SHA-256 / ba81dc8785f3eb10330a037ce768b6cd708e1eaf456538b9f35ae983bc2ec660
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:48:44.715948+00:00.
Case digest / 1d60e7eaad235b5e47dee664ca46ab72cbac4a8afadec73013fe2aa40de6611d