{"abstract":"Evicted mass disappears, so counts underestimate and the overestimate-only property is lost.","category":"Probabilistic sketches","checks":9,"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].","evaluation_group":"w2-probabilistic_sketches-space-saving","failed_approach":"Inheriting the victim count without adding one ignores the newcomer's own occurrence.","family":"w2-probabilistic_sketches-space-saving-inherit-count","id":"FA-73116","implementations":{"attempt":{"sha256":"ef581d58cb2eba36ac24521eae71ce09de7778a59540d5ea8f8430c878b344e7","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    S = {}\n    tick = 0\n    for item in x['stream']:\n        tick += 1\n        if item in S:\n            S[item][0] += 1\n            S[item][2] = tick\n        elif len(S) < k:\n            S[item] = [1, 0, tick]\n        else:\n            victim = min(S, key=lambda key: (S[key][0], S[key][2]))\n            cnt = S.pop(victim)[0]\n            S[item] = [cnt, cnt, tick]\n    Ntot = len(x['stream'])\n    num, den = x['phi']\n    rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))\n    guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)\n    return [rows, guaranteed]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},\n   [[['a', 9, 3], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},\n   [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},\n   [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},\n   [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},\n   [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},\n   [[['a', 10, 4], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},\n   [[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},\n   [[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},\n   [[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},\n   [[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['d',\n               'b',\n               'a',\n               'a',\n               'a',\n               'e',\n               'c',\n               'a',\n               'f',\n               'c',\n               'a',\n               'e',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'd',\n               'b',\n               'c',\n               'c',\n               'c',\n               'a',\n               'd',\n               'c',\n               'b',\n               'd',\n               'b',\n               'a',\n               'b']},\n   [[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'c',\n               'c',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'c',\n               'd',\n               'a']},\n   [[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},\n   [[['c', 3, 2], ['a', 2, 0]], ['a']]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},\n   [[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['d',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c',\n               'b',\n               'a',\n               'b',\n               'a']},\n   [[['a', 9, 7], ['b', 9, 7]], []]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'f',\n               'f',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'a',\n               'a',\n               'b']},\n   [[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'c',\n               'c',\n               'e',\n               'a',\n               'f',\n               'c',\n               'c',\n               'e',\n               'd',\n               'f',\n               'b',\n               'a',\n               'a',\n               'c',\n               'b',\n               'b']},\n   [[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'd',\n               'e',\n               'a',\n               'd',\n               'a',\n               'g',\n               'a',\n               'c',\n               'g',\n               'c',\n               'b']},\n   [[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},\n   [[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c']},\n   [[['a', 13, 0], ['c', 6, 5]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'f',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'c',\n               'f',\n               'f',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'b',\n               'a',\n               'd',\n               'a',\n               'a']},\n   [[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'd',\n               'f',\n               'a',\n               'd',\n               'a',\n               'a',\n               'g']},\n   [[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},\n   [[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"529ca7f324adcd01655d2547c475d145ca5113a773aa8be8af3fc45afaf349d2","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    S = {}\n    tick = 0\n    for item in x['stream']:\n        tick += 1\n        if item in S:\n            S[item][0] += 1\n            S[item][2] = tick\n        elif len(S) < k:\n            S[item] = [1, 0, tick]\n        else:\n            victim = min(S, key=lambda key: (S[key][0], S[key][2]))\n            cnt = S.pop(victim)[0]\n            S[item] = [1, cnt, tick]\n    Ntot = len(x['stream'])\n    num, den = x['phi']\n    rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))\n    guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)\n    return [rows, guaranteed]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},\n   [[['a', 9, 3], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},\n   [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},\n   [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},\n   [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},\n   [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},\n   [[['a', 10, 4], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},\n   [[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},\n   [[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},\n   [[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},\n   [[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['d',\n               'b',\n               'a',\n               'a',\n               'a',\n               'e',\n               'c',\n               'a',\n               'f',\n               'c',\n               'a',\n               'e',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'd',\n               'b',\n               'c',\n               'c',\n               'c',\n               'a',\n               'd',\n               'c',\n               'b',\n               'd',\n               'b',\n               'a',\n               'b']},\n   [[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'c',\n               'c',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'c',\n               'd',\n               'a']},\n   [[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},\n   [[['c', 3, 2], ['a', 2, 0]], ['a']]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},\n   [[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['d',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c',\n               'b',\n               'a',\n               'b',\n               'a']},\n   [[['a', 9, 7], ['b', 9, 7]], []]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'f',\n               'f',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'a',\n               'a',\n               'b']},\n   [[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'c',\n               'c',\n               'e',\n               'a',\n               'f',\n               'c',\n               'c',\n               'e',\n               'd',\n               'f',\n               'b',\n               'a',\n               'a',\n               'c',\n               'b',\n               'b']},\n   [[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'd',\n               'e',\n               'a',\n               'd',\n               'a',\n               'g',\n               'a',\n               'c',\n               'g',\n               'c',\n               'b']},\n   [[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},\n   [[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c']},\n   [[['a', 13, 0], ['c', 6, 5]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'f',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'c',\n               'f',\n               'f',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'b',\n               'a',\n               'd',\n               'a',\n               'a']},\n   [[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'd',\n               'f',\n               'a',\n               'd',\n               'a',\n               'a',\n               'g']},\n   [[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},\n   [[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"ba81dc8785f3eb10330a037ce768b6cd708e1eaf456538b9f35ae983bc2ec660","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    k = x['k']\n    S = {}\n    tick = 0\n    for item in x['stream']:\n        tick += 1\n        if item in S:\n            S[item][0] += 1\n            S[item][2] = tick\n        elif len(S) < k:\n            S[item] = [1, 0, tick]\n        else:\n            victim = min(S, key=lambda key: (S[key][0], S[key][2]))\n            cnt = S.pop(victim)[0]\n            S[item] = [cnt + 1, cnt, tick]\n    Ntot = len(x['stream'])\n    num, den = x['phi']\n    rows = sorted(([key, v[0], v[1]] for key, v in S.items()), key=lambda row: (-row[1], row[0]))\n    guaranteed = sorted(key for key, v in S.items() if (v[0] - v[1]) * den > num * Ntot)\n    return [rows, guaranteed]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'b', 'd', 'b', 'c', 'a', 'b', 'a', 'a', 'a', 'a', 'a', 'b']},\n   [[['a', 9, 3], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'e', 'b', 'e', 'f', 'a', 'b', 'a', 'd', 'a', 'a', 'b', 'a', 'a', 'a']},\n   [[['a', 8, 1], ['b', 4, 2], ['d', 3, 2]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a', 'a', 'e', 'b', 'e', 'a', 'a', 'e', 'a', 'b', 'b', 'a', 'c', 'a', 'a']},\n   [[['a', 8, 0], ['c', 4, 3], ['b', 3, 0]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'a', 'a', 'd', 'b', 'b', 'a', 'c', 'b', 'b', 'a', 'g', 'a', 'a']},\n   [[['a', 7, 0], ['b', 5, 0], ['g', 2, 1], ['c', 1, 0]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r']},\n   [[['q', 2, 0], ['r', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a', 'b', 'a', 'a', 'c', 'b', 'b', 'e', 'a', 'b', 'a', 'a', 'a', 'b', 'a', 'a']},\n   [[['a', 10, 4], ['b', 6, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['f', 'a', 'a', 'f', 'a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'b', 'b', 'a', 'a']},\n   [[['a', 10, 0], ['b', 4, 0], ['f', 2, 0]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['b', 'a', 'd', 'a', 'c', 'f', 'a', 'e', 'c', 'a', 'a', 'a', 'c', 'b', 'c', 'b']},\n   [[['a', 6, 0], ['b', 5, 3], ['c', 5, 2]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['d', 'b', 'g', 'b', 'a', 'a', 'a', 'g', 'a', 'f', 'b', 'a', 'd', 'a', 'a', 'a']},\n   [[['a', 8, 0], ['b', 3, 0], ['d', 3, 2], ['f', 2, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r']},\n   [[['r', 3, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 4]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['d',\n               'b',\n               'a',\n               'a',\n               'a',\n               'e',\n               'c',\n               'a',\n               'f',\n               'c',\n               'a',\n               'e',\n               'b',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 9, 0], ['b', 4, 3], ['e', 4, 3]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'd',\n               'b',\n               'c',\n               'c',\n               'c',\n               'a',\n               'd',\n               'c',\n               'b',\n               'd',\n               'b',\n               'a',\n               'b']},\n   [[['a', 6, 5], ['b', 6, 3], ['d', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'c',\n               'c',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'c',\n               'd',\n               'a']},\n   [[['a', 8, 0], ['c', 5, 0], ['b', 3, 0], ['d', 1, 0]], ['a', 'c']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c']},\n   [[['c', 3, 2], ['a', 2, 0]], ['a']]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r']},\n   [[['r', 4, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['d',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c',\n               'b',\n               'a',\n               'b',\n               'a']},\n   [[['a', 9, 7], ['b', 9, 7]], []]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'f',\n               'f',\n               'c',\n               'c',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'a',\n               'a',\n               'b']},\n   [[['a', 9, 0], ['b', 5, 2], ['c', 4, 1]], ['a']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'c',\n               'c',\n               'e',\n               'a',\n               'f',\n               'c',\n               'c',\n               'e',\n               'd',\n               'f',\n               'b',\n               'a',\n               'a',\n               'c',\n               'b',\n               'b']},\n   [[['b', 7, 4], ['a', 6, 4], ['c', 5, 4]], []]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'b',\n               'a',\n               'd',\n               'e',\n               'a',\n               'd',\n               'a',\n               'g',\n               'a',\n               'c',\n               'g',\n               'c',\n               'b']},\n   [[['a', 8, 0], ['c', 4, 2], ['b', 3, 2], ['g', 3, 1]], ['a']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd']},\n   [[['c', 3, 2], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r']},\n   [[['r', 3, 2], ['p', 2, 0]], ['p']]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r']},\n   [[['r', 5, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]],\n [['skewed stream 0 k=2',\n   {'k': 2,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'e',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'a',\n               'd',\n               'c']},\n   [[['a', 13, 0], ['c', 6, 5]], ['a']]],\n  ['skewed stream 1 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'a',\n               'b',\n               'a',\n               'f',\n               'a',\n               'a',\n               'a',\n               'a']},\n   [[['a', 12, 0], ['b', 5, 0], ['f', 2, 1]], ['a', 'b']]],\n  ['skewed stream 2 k=3',\n   {'k': 3,\n    'phi': [1, 4],\n    'stream': ['a',\n               'b',\n               'a',\n               'a',\n               'a',\n               'c',\n               'f',\n               'f',\n               'a',\n               'a',\n               'a',\n               'b',\n               'b',\n               'b',\n               'b',\n               'a',\n               'd',\n               'a',\n               'a']},\n   [[['a', 10, 0], ['b', 5, 1], ['d', 4, 3]], ['a']]],\n  ['skewed stream 3 k=4',\n   {'k': 4,\n    'phi': [1, 4],\n    'stream': ['b',\n               'c',\n               'a',\n               'b',\n               'a',\n               'b',\n               'a',\n               'b',\n               'b',\n               'a',\n               'a',\n               'c',\n               'd',\n               'f',\n               'a',\n               'd',\n               'a',\n               'a',\n               'g']},\n   [[['a', 8, 0], ['b', 5, 0], ['d', 3, 2], ['g', 3, 2]], ['a', 'b']]],\n  ['tie eviction by age',\n   {'k': 2, 'phi': [1, 3], 'stream': ['b', 'a', 'b', 'a', 'c', 'd', 'b']},\n   [[['b', 4, 3], ['d', 3, 2]], []]],\n  ['boundary threshold',\n   {'k': 2, 'phi': [3, 7], 'stream': ['a', 'a', 'a', 'b', 'b', 'b', 'c']},\n   [[['c', 4, 3], ['b', 3, 0]], []]],\n  ['refresh on hit',\n   {'k': 2, 'phi': [1, 10], 'stream': ['x', 'y', 'x', 'z', 'y', 'w']},\n   [[['w', 3, 2], ['y', 3, 2]], ['w', 'y']]],\n  ['equal counts different recency',\n   {'k': 2, 'phi': [1, 4], 'stream': ['p', 'q', 'q', 'p', 'r', 'q']},\n   [[['q', 3, 2], ['r', 3, 2]], []]],\n  ['no eviction',\n   {'k': 3, 'phi': [1, 5], 'stream': ['q', 'r', 'q', 's', 'r', 'r', 'r', 'r', 'r']},\n   [[['r', 6, 0], ['q', 2, 0], ['s', 1, 0]], ['q', 'r']]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-probabilistic_sketches-space-saving-inherit-count","generated_at":"2026-09-29T14:48:44.628171+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Top-k dashboards and abuse detectors use Space-Saving because its per-item error bound lets them separate guaranteed heavy hitters from possible ones.","repair":"Set the new count to victim count + 1.","root_cause":"The replacement entry starts at count 1 instead of inheriting the victim count plus one.","sha256":"e60e3f39b3dae675f0783d00c9c0ad3ebcaef2389447adbecec4ecbef61badbb","title":"Space-Saving heavy hitters: newcomer restarts at one · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.801,"exit_code":1,"observations":[{"actual":[[["a",7,2],["b",5,0]],["a","b"]],"check":"skewed stream 0 k=2","expected":[[["a",9,3],["b",6,4]],["a"]],"passed":false},{"actual":[[["a",7,1],["e",2,0],["b",1,1]],["a"]],"check":"skewed stream 1 k=3","expected":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"passed":false},{"actual":[[["a",8,0],["b",3,0],["c",3,3]],["a"]],"check":"skewed stream 2 k=3","expected":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"passed":false},{"actual":[[["a",7,0],["b",5,0],["c",1,0],["g",1,1]],["a","b"]],"check":"skewed stream 3 k=4","expected":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"passed":false},{"actual":[[["c",2,2],["d",2,2]],[]],"check":"tie eviction by age","expected":[[["c",3,2],["d",3,2]],[]],"passed":false},{"actual":[[["b",3,0],["c",3,3]],[]],"check":"boundary threshold","expected":[[["c",4,3],["b",3,0]],[]],"passed":false},{"actual":[[["x",2,0],["w",1,1]],["x"]],"check":"refresh on hit","expected":[[["w",3,2],["y",3,2]],["w","y"]],"passed":false},{"actual":[[["q",2,2],["r",2,2]],[]],"check":"equal counts different recency","expected":[[["q",3,2],["r",3,2]],[]],"passed":false},{"actual":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"check":"no eviction","expected":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"skewed stream 0 k=2\", \"actual\": [[[\"a\", 7, 2], [\"b\", 5, 0]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 1 k=3\", \"actual\": [[[\"a\", 7, 1], [\"e\", 2, 0], [\"b\", 1, 1]], [\"a\"]], \"expected\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 2 k=3\", \"actual\": [[[\"a\", 8, 0], [\"b\", 3, 0], [\"c\", 3, 3]], [\"a\"]], \"expected\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 3 k=4\", \"actual\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"c\", 1, 0], [\"g\", 1, 1]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"passed\": false}, {\"check\": \"tie eviction by age\", \"actual\": [[[\"c\", 2, 2], [\"d\", 2, 2]], []], \"expected\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"passed\": false}, {\"check\": \"boundary threshold\", \"actual\": [[[\"b\", 3, 0], [\"c\", 3, 3]], []], \"expected\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"passed\": false}, {\"check\": \"refresh on hit\", \"actual\": [[[\"x\", 2, 0], [\"w\", 1, 1]], [\"x\"]], \"expected\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"passed\": false}, {\"check\": \"equal counts different recency\", \"actual\": [[[\"q\", 2, 2], [\"r\", 2, 2]], []], \"expected\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"passed\": false}, {\"check\": \"no eviction\", \"actual\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"expected\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.119,"exit_code":1,"observations":[{"actual":[[["a",6,1],["b",5,0]],["a","b"]],"check":"skewed stream 0 k=2","expected":[[["a",9,3],["b",6,4]],["a"]],"passed":false},{"actual":[[["a",7,1],["e",2,0],["b",1,1]],["a"]],"check":"skewed stream 1 k=3","expected":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"passed":false},{"actual":[[["a",8,0],["b",3,0],["c",1,3]],["a"]],"check":"skewed stream 2 k=3","expected":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"passed":false},{"actual":[[["a",7,0],["b",5,0],["c",1,0],["g",1,1]],["a","b"]],"check":"skewed stream 3 k=4","expected":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"passed":false},{"actual":[[["a",2,0],["d",1,1]],[]],"check":"tie eviction by age","expected":[[["c",3,2],["d",3,2]],[]],"passed":false},{"actual":[[["b",3,0],["c",1,3]],[]],"check":"boundary threshold","expected":[[["c",4,3],["b",3,0]],[]],"passed":false},{"actual":[[["x",2,0],["w",1,1]],["x"]],"check":"refresh on hit","expected":[[["w",3,2],["y",3,2]],["w","y"]],"passed":false},{"actual":[[["p",2,0],["q",1,1]],["p"]],"check":"equal counts different recency","expected":[[["q",3,2],["r",3,2]],[]],"passed":false},{"actual":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"check":"no eviction","expected":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"skewed stream 0 k=2\", \"actual\": [[[\"a\", 6, 1], [\"b\", 5, 0]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 1 k=3\", \"actual\": [[[\"a\", 7, 1], [\"e\", 2, 0], [\"b\", 1, 1]], [\"a\"]], \"expected\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 2 k=3\", \"actual\": [[[\"a\", 8, 0], [\"b\", 3, 0], [\"c\", 1, 3]], [\"a\"]], \"expected\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"passed\": false}, {\"check\": \"skewed stream 3 k=4\", \"actual\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"c\", 1, 0], [\"g\", 1, 1]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"passed\": false}, {\"check\": \"tie eviction by age\", \"actual\": [[[\"a\", 2, 0], [\"d\", 1, 1]], []], \"expected\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"passed\": false}, {\"check\": \"boundary threshold\", \"actual\": [[[\"b\", 3, 0], [\"c\", 1, 3]], []], \"expected\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"passed\": false}, {\"check\": \"refresh on hit\", \"actual\": [[[\"x\", 2, 0], [\"w\", 1, 1]], [\"x\"]], \"expected\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"passed\": false}, {\"check\": \"equal counts different recency\", \"actual\": [[[\"p\", 2, 0], [\"q\", 1, 1]], [\"p\"]], \"expected\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"passed\": false}, {\"check\": \"no eviction\", \"actual\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"expected\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":42.275,"exit_code":0,"observations":[{"actual":[[["a",9,3],["b",6,4]],["a"]],"check":"skewed stream 0 k=2","expected":[[["a",9,3],["b",6,4]],["a"]],"passed":true},{"actual":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"check":"skewed stream 1 k=3","expected":[[["a",8,1],["b",4,2],["d",3,2]],["a"]],"passed":true},{"actual":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"check":"skewed stream 2 k=3","expected":[[["a",8,0],["c",4,3],["b",3,0]],["a"]],"passed":true},{"actual":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"check":"skewed stream 3 k=4","expected":[[["a",7,0],["b",5,0],["g",2,1],["c",1,0]],["a","b"]],"passed":true},{"actual":[[["c",3,2],["d",3,2]],[]],"check":"tie eviction by age","expected":[[["c",3,2],["d",3,2]],[]],"passed":true},{"actual":[[["c",4,3],["b",3,0]],[]],"check":"boundary threshold","expected":[[["c",4,3],["b",3,0]],[]],"passed":true},{"actual":[[["w",3,2],["y",3,2]],["w","y"]],"check":"refresh on hit","expected":[[["w",3,2],["y",3,2]],["w","y"]],"passed":true},{"actual":[[["q",3,2],["r",3,2]],[]],"check":"equal counts different recency","expected":[[["q",3,2],["r",3,2]],[]],"passed":true},{"actual":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"check":"no eviction","expected":[[["q",2,0],["r",2,0],["s",1,0]],["q","r"]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"skewed stream 0 k=2\", \"actual\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"expected\": [[[\"a\", 9, 3], [\"b\", 6, 4]], [\"a\"]], \"passed\": true}, {\"check\": \"skewed stream 1 k=3\", \"actual\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"expected\": [[[\"a\", 8, 1], [\"b\", 4, 2], [\"d\", 3, 2]], [\"a\"]], \"passed\": true}, {\"check\": \"skewed stream 2 k=3\", \"actual\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"expected\": [[[\"a\", 8, 0], [\"c\", 4, 3], [\"b\", 3, 0]], [\"a\"]], \"passed\": true}, {\"check\": \"skewed stream 3 k=4\", \"actual\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"expected\": [[[\"a\", 7, 0], [\"b\", 5, 0], [\"g\", 2, 1], [\"c\", 1, 0]], [\"a\", \"b\"]], \"passed\": true}, {\"check\": \"tie eviction by age\", \"actual\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"expected\": [[[\"c\", 3, 2], [\"d\", 3, 2]], []], \"passed\": true}, {\"check\": \"boundary threshold\", \"actual\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"expected\": [[[\"c\", 4, 3], [\"b\", 3, 0]], []], \"passed\": true}, {\"check\": \"refresh on hit\", \"actual\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"expected\": [[[\"w\", 3, 2], [\"y\", 3, 2]], [\"w\", \"y\"]], \"passed\": true}, {\"check\": \"equal counts different recency\", \"actual\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"expected\": [[[\"q\", 3, 2], [\"r\", 3, 2]], []], \"passed\": true}, {\"check\": \"no eviction\", \"actual\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"expected\": [[[\"q\", 2, 0], [\"r\", 2, 0], [\"s\", 1, 0]], [\"q\", \"r\"]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}