FA-73076 / Probabilistic sketches / Open access
Count sketch frequency estimation: estimate averages rows · case 01
A single heavily colliding row skews the estimate instead of being outvoted.
ROOT CAUSE
The estimator takes the mean across rows instead of the median.
VERIFIED REPAIR
Take the median of the signed row values.
Unsuccessful approach: Picking the middle row of unsorted values is not a median.
Case contract
Input {w, d, stream, queries}; stream entries are [key, signed count]. Row r uses bucket ((A_r key + B_r) mod 2^31-1) mod w and sign +1 when ((C_r key + D_r) mod 2^31-1) is odd, else -1, from an independent hash. Updates add sign*count. A query returns the median over rows of sign*cell; for even d the median is the mean of the two middle values. Negative estimates are returned unchanged (turnstile streams).
Why this case matters
Count sketches estimate signed frequencies in turnstile streams (inserts and deletes); their unbiasedness depends on independent signs and a median across rows.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
w = x['w']
d = x['d']
P = 2147483647
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941]
B = [12345, 1013904223, 7, 99991, 31337, 424242]
C = [2027373281, 1370461471, 1234567891, 1987654321, 1111111121, 1777777777]
D = [3, 5, 11, 17, 23, 29]
t = [[0] * w for _ in range(d)]
def bucket(r, key):
return (A[r] * key + B[r]) % P % w
def sign(r, key):
return 1 if ((C[r] * key + D[r]) % P) & 1 else -1
for key, cnt in x['stream']:
for r in range(d):
t[r][bucket(r, key)] += sign(r, key) * cnt
out = []
for key in x['queries']:
vals = sorted(sign(r, key) * t[r][bucket(r, key)] for r in range(d))
out.append(sum(vals) / d)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=4 d=3',
{'d': 3,
'queries': [23, 53, 27, 24, 14, 100],
'stream': [[23, -1], [53, 7], [27, 5], [24, -1], [14, 8], [12, 6], [11, 8], [23, 6]],
'w': 4},
[-1, 9, -3, -9, 9, -6]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [26, 55, 10, 15, 19, 100],
'stream': [[26, 5], [55, 1], [10, 6], [15, 5], [19, 8], [8, 9], [59, 0], [26, 6]],
'w': 5},
[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [13, 55, 20, 4, 57, 100],
'stream': [[13, 6], [55, 6], [20, 2], [4, 6], [57, -3], [56, 7], [34, 3], [13, 6]],
'w': 3},
[12, 15, 2, 6, -3, -6]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [52, 50, 14, 47, 13, 100],
'stream': [[52, -2], [50, 8], [14, 7], [47, 7], [13, 1], [6, 3], [2, -1], [52, 6]],
'w': 6},
[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [7, 36, 53, 37, 29, 100],
'stream': [[7, 8], [36, 2], [53, 4], [37, 4], [29, -1], [16, -1], [56, -3], [7, 6]],
'w': 4},
[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [2, 31, 48, 20, 24, 100],
'stream': [[2, 8], [31, 5], [48, 1], [20, 1], [24, -1], [35, 3], [56, 9], [2, 6]],
'w': 2},
[12, -2, -12, 2, 12, 2]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -3]], 'w': 3},
[0, -3]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [47, 24, 9, 42, 45, 101],
'stream': [[47, 5], [24, 3], [9, 3], [42, -1], [45, 0], [39, 9], [50, 1], [47, 7]],
'w': 4},
[15, 4, 3, 2, -3, 0]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [47, 44, 11, 17, 43, 101],
'stream': [[47, 4], [44, 8], [11, 1], [17, 4], [43, -2], [40, 8], [35, 9], [47, 7]],
'w': 5},
[11.0, 5.0, 9.5, 8.0, -2.5, -1.0]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [50, 54, 17, 44, 8, 101],
'stream': [[50, 9], [54, 8], [17, 0], [44, -2], [8, -2], [19, -3], [37, -3], [50, 7]],
'w': 3},
[13, 6, -3, 1, 0, 5]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [53, 40, 34, 19, 50, 101],
'stream': [[53, 0], [40, 6], [34, 5], [19, 9], [50, 3], [41, 4], [16, -3], [53, 7]],
'w': 6},
[0.0, 2.5, 5.0, 5.0, 2.5, -1.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [37, 49, 24, 52, 33, 101],
'stream': [[37, 4], [49, -3], [24, -2], [52, 9], [33, 5], [12, -1], [35, -2], [37, 7]],
'w': 4},
[10.5, -2.0, -3.0, 7.0, 3.5, -5.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [33, 40, 3, 43, 8, 101],
'stream': [[33, 1], [40, 2], [3, 8], [43, 8], [8, 9], [46, 0], [19, -1], [33, 7]],
'w': 2},
[7, 11, 11, 7, -7, -11]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -4]], 'w': 3},
[0, -4]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [26, 43, 31, 44, 30, 102],
'stream': [[26, 7], [43, 0], [31, -2], [44, 9], [30, -1], [10, -1], [41, 3], [26, 8]],
'w': 4},
[12, 1, -2, 7, -1, -12]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [52, 33, 27, 41, 23, 102],
'stream': [[52, 6], [33, -2], [27, 7], [41, 8], [23, 4], [10, -1], [17, 2], [52, 8]],
'w': 5},
[19.0, -11.5, 4.5, 14.0, 4.0, 0.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [30, 59, 54, 34, 46, 102],
'stream': [[30, -3], [59, 2], [54, 7], [34, 3], [46, 4], [10, -2], [43, 6], [30, 8]],
'w': 3},
[12, 6, 12, 1, 3, -6]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [31, 58, 1, 13, 44, 102],
'stream': [[31, 6], [58, 9], [1, -3], [13, 8], [44, 7], [24, 0], [32, -3], [31, 8]],
'w': 6},
[17.5, 10.5, 1.0, 6.5, 15.5, -6.5]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [42, 39, 12, 48, 7, 102],
'stream': [[42, 2], [39, 0], [12, 0], [48, 1], [7, 1], [27, 8], [19, 0], [42, 8]],
'w': 4},
[10.0, 0.5, -0.5, 1.0, 1.0, -1.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [52, 26, 2, 12, 54, 102],
'stream': [[52, -2], [26, 1], [2, 9], [12, 1], [54, 4], [19, 1], [29, 4], [52, 8]],
'w': 2},
[6, -5, 11, 6, 0, -6]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -5]], 'w': 3},
[0, -5]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [17, 20, 22, 7, 59, 103],
'stream': [[17, -2], [20, 3], [22, 1], [7, 6], [59, 2], [53, 4], [21, -1], [17, 9]],
'w': 4},
[4, 0, -2, 3, -4, 3]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [38, 14, 1, 21, 19, 103],
'stream': [[38, -2], [14, 2], [1, -3], [21, 1], [19, 1], [7, 4], [36, 3], [38, 9]],
'w': 5},
[5.0, 0.0, -3.0, 1.5, -6.0, 0.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [47, 31, 6, 26, 18, 103],
'stream': [[47, -3], [31, 0], [6, 6], [26, 6], [18, 2], [38, 9], [10, 9], [47, 9]],
'w': 3},
[10, 0, 8, 8, 2, -9]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [2, 8, 16, 10, 59, 103],
'stream': [[2, 0], [8, 5], [16, -2], [10, 0], [59, -1], [45, -2], [20, -3], [2, 9]],
'w': 6},
[9.0, 6.5, -2.0, 0.0, -2.5, -9.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [42, 41, 28, 10, 22, 103],
'stream': [[42, 5], [41, 1], [28, 9], [10, 6], [22, -3], [56, 5], [34, 5], [42, 9]],
'w': 4},
[12.5, -4.0, 8.5, 6.0, -0.5, -0.5]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [27, 30, 53, 34, 37, 103],
'stream': [[27, 8], [30, 5], [53, 2], [34, 9], [37, -3], [38, -3], [51, 1], [27, 9]],
'w': 2},
[12, 14, 10, 14, 12, 12]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -6]], 'w': 3},
[0, -6]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [49, 2, 6, 18, 34, 104],
'stream': [[49, -1], [2, 7], [6, 0], [18, 7], [34, 7], [8, 5], [1, 3], [49, 10]],
'w': 4},
[6, 0, 4, 7, 7, -3]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [56, 42, 28, 49, 48, 104],
'stream': [[56, -1], [42, -2], [28, 1], [49, -3], [48, 0], [26, 3], [12, 7], [56, 10]],
'w': 5},
[10.5, -3.5, 2.5, -3.5, -2.0, -3.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [41, 12, 50, 46, 3, 104],
'stream': [[41, 0], [12, 1], [50, 3], [46, 1], [3, 4], [30, -2], [32, -3], [41, 10]],
'w': 3},
[12, 4, 4, 4, 4, -1]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [15, 5, 4, 19, 30, 104],
'stream': [[15, 2], [5, -3], [4, 5], [19, -2], [30, -2], [40, -3], [23, 7], [15, 10]],
'w': 6},
[12.0, -3.0, 1.0, -2.0, -4.5, -2.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [5, 41, 39, 54, 1, 104],
'stream': [[5, 0], [41, 5], [39, 2], [54, 1], [1, -2], [52, 7], [13, 5], [5, 10]],
'w': 4},
[12.0, 4.0, 7.0, -4.0, -1.0, -2.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [57, 35, 2, 54, 27, 104],
'stream': [[57, 8], [35, 4], [2, -3], [54, 3], [27, 4], [38, 9], [48, 4], [57, 10]],
'w': 2},
[22, 22, 3, 23, 22, 4]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -7]], 'w': 3},
[0, -7]]]]
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 |
|---|---|---|---|
| stream 0 w=4 d=3 | [1.0, 8.666666666666666, -1.6666666666666667, -4.666666666666667, 10.0, -5.0] | [-1, 9, -3, -9, 9, -6] | Failed |
| stream 1 w=5 d=4 | [13.75, -0.5, 8.5, 7.75, 8.0, -1.0] | [11.5, -2.0, 5.5, 5.0, 8.0, 0.0] | Failed |
| stream 2 w=3 d=5 | [15.2, 14.8, 4.0, 12.6, 1.8, -8.4] | [12, 15, 2, 6, -3, -6] | Failed |
| stream 3 w=6 d=2 | [4.5, 7.5, 6.5, 9.0, 8.0, -6.0] | [4.5, 7.5, 6.5, 9.0, 8.0, -6.0] | Passed |
| stream 4 w=4 d=6 | [15.333333333333334, 6.666666666666667, 7.833333333333333, 7.333333333333333, 1.8333333333333333, -2.5] | [15.0, 3.5, 5.0, 4.5, 0.5, -2.5] | Failed |
| stream 5 w=2 d=3 | [9.333333333333334, 2.6666666666666665, -8.666666666666666, 4.0, 10.0, 0.0] | [12, -2, -12, 2, 12, 2] | Failed |
| deletions cancel | [1.0, -3.0] | [0, -3] | Failed |
SHA-256 / 1e75983fdf2c5a1f1a358da9bb594554d1ff1f295aba4f962e7ad723e84721c0
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
w = x['w']
d = x['d']
P = 2147483647
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941]
B = [12345, 1013904223, 7, 99991, 31337, 424242]
C = [2027373281, 1370461471, 1234567891, 1987654321, 1111111121, 1777777777]
D = [3, 5, 11, 17, 23, 29]
t = [[0] * w for _ in range(d)]
def bucket(r, key):
return (A[r] * key + B[r]) % P % w
def sign(r, key):
return 1 if ((C[r] * key + D[r]) % P) & 1 else -1
for key, cnt in x['stream']:
for r in range(d):
t[r][bucket(r, key)] += sign(r, key) * cnt
out = []
for key in x['queries']:
vals = sorted(sign(r, key) * t[r][bucket(r, key)] for r in range(d))
raw = [sign(r, key) * t[r][bucket(r, key)] for r in range(d)]
out.append(raw[d // 2])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=4 d=3',
{'d': 3,
'queries': [23, 53, 27, 24, 14, 100],
'stream': [[23, -1], [53, 7], [27, 5], [24, -1], [14, 8], [12, 6], [11, 8], [23, 6]],
'w': 4},
[-1, 9, -3, -9, 9, -6]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [26, 55, 10, 15, 19, 100],
'stream': [[26, 5], [55, 1], [10, 6], [15, 5], [19, 8], [8, 9], [59, 0], [26, 6]],
'w': 5},
[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [13, 55, 20, 4, 57, 100],
'stream': [[13, 6], [55, 6], [20, 2], [4, 6], [57, -3], [56, 7], [34, 3], [13, 6]],
'w': 3},
[12, 15, 2, 6, -3, -6]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [52, 50, 14, 47, 13, 100],
'stream': [[52, -2], [50, 8], [14, 7], [47, 7], [13, 1], [6, 3], [2, -1], [52, 6]],
'w': 6},
[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [7, 36, 53, 37, 29, 100],
'stream': [[7, 8], [36, 2], [53, 4], [37, 4], [29, -1], [16, -1], [56, -3], [7, 6]],
'w': 4},
[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [2, 31, 48, 20, 24, 100],
'stream': [[2, 8], [31, 5], [48, 1], [20, 1], [24, -1], [35, 3], [56, 9], [2, 6]],
'w': 2},
[12, -2, -12, 2, 12, 2]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -3]], 'w': 3},
[0, -3]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [47, 24, 9, 42, 45, 101],
'stream': [[47, 5], [24, 3], [9, 3], [42, -1], [45, 0], [39, 9], [50, 1], [47, 7]],
'w': 4},
[15, 4, 3, 2, -3, 0]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [47, 44, 11, 17, 43, 101],
'stream': [[47, 4], [44, 8], [11, 1], [17, 4], [43, -2], [40, 8], [35, 9], [47, 7]],
'w': 5},
[11.0, 5.0, 9.5, 8.0, -2.5, -1.0]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [50, 54, 17, 44, 8, 101],
'stream': [[50, 9], [54, 8], [17, 0], [44, -2], [8, -2], [19, -3], [37, -3], [50, 7]],
'w': 3},
[13, 6, -3, 1, 0, 5]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [53, 40, 34, 19, 50, 101],
'stream': [[53, 0], [40, 6], [34, 5], [19, 9], [50, 3], [41, 4], [16, -3], [53, 7]],
'w': 6},
[0.0, 2.5, 5.0, 5.0, 2.5, -1.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [37, 49, 24, 52, 33, 101],
'stream': [[37, 4], [49, -3], [24, -2], [52, 9], [33, 5], [12, -1], [35, -2], [37, 7]],
'w': 4},
[10.5, -2.0, -3.0, 7.0, 3.5, -5.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [33, 40, 3, 43, 8, 101],
'stream': [[33, 1], [40, 2], [3, 8], [43, 8], [8, 9], [46, 0], [19, -1], [33, 7]],
'w': 2},
[7, 11, 11, 7, -7, -11]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -4]], 'w': 3},
[0, -4]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [26, 43, 31, 44, 30, 102],
'stream': [[26, 7], [43, 0], [31, -2], [44, 9], [30, -1], [10, -1], [41, 3], [26, 8]],
'w': 4},
[12, 1, -2, 7, -1, -12]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [52, 33, 27, 41, 23, 102],
'stream': [[52, 6], [33, -2], [27, 7], [41, 8], [23, 4], [10, -1], [17, 2], [52, 8]],
'w': 5},
[19.0, -11.5, 4.5, 14.0, 4.0, 0.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [30, 59, 54, 34, 46, 102],
'stream': [[30, -3], [59, 2], [54, 7], [34, 3], [46, 4], [10, -2], [43, 6], [30, 8]],
'w': 3},
[12, 6, 12, 1, 3, -6]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [31, 58, 1, 13, 44, 102],
'stream': [[31, 6], [58, 9], [1, -3], [13, 8], [44, 7], [24, 0], [32, -3], [31, 8]],
'w': 6},
[17.5, 10.5, 1.0, 6.5, 15.5, -6.5]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [42, 39, 12, 48, 7, 102],
'stream': [[42, 2], [39, 0], [12, 0], [48, 1], [7, 1], [27, 8], [19, 0], [42, 8]],
'w': 4},
[10.0, 0.5, -0.5, 1.0, 1.0, -1.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [52, 26, 2, 12, 54, 102],
'stream': [[52, -2], [26, 1], [2, 9], [12, 1], [54, 4], [19, 1], [29, 4], [52, 8]],
'w': 2},
[6, -5, 11, 6, 0, -6]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -5]], 'w': 3},
[0, -5]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [17, 20, 22, 7, 59, 103],
'stream': [[17, -2], [20, 3], [22, 1], [7, 6], [59, 2], [53, 4], [21, -1], [17, 9]],
'w': 4},
[4, 0, -2, 3, -4, 3]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [38, 14, 1, 21, 19, 103],
'stream': [[38, -2], [14, 2], [1, -3], [21, 1], [19, 1], [7, 4], [36, 3], [38, 9]],
'w': 5},
[5.0, 0.0, -3.0, 1.5, -6.0, 0.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [47, 31, 6, 26, 18, 103],
'stream': [[47, -3], [31, 0], [6, 6], [26, 6], [18, 2], [38, 9], [10, 9], [47, 9]],
'w': 3},
[10, 0, 8, 8, 2, -9]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [2, 8, 16, 10, 59, 103],
'stream': [[2, 0], [8, 5], [16, -2], [10, 0], [59, -1], [45, -2], [20, -3], [2, 9]],
'w': 6},
[9.0, 6.5, -2.0, 0.0, -2.5, -9.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [42, 41, 28, 10, 22, 103],
'stream': [[42, 5], [41, 1], [28, 9], [10, 6], [22, -3], [56, 5], [34, 5], [42, 9]],
'w': 4},
[12.5, -4.0, 8.5, 6.0, -0.5, -0.5]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [27, 30, 53, 34, 37, 103],
'stream': [[27, 8], [30, 5], [53, 2], [34, 9], [37, -3], [38, -3], [51, 1], [27, 9]],
'w': 2},
[12, 14, 10, 14, 12, 12]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -6]], 'w': 3},
[0, -6]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [49, 2, 6, 18, 34, 104],
'stream': [[49, -1], [2, 7], [6, 0], [18, 7], [34, 7], [8, 5], [1, 3], [49, 10]],
'w': 4},
[6, 0, 4, 7, 7, -3]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [56, 42, 28, 49, 48, 104],
'stream': [[56, -1], [42, -2], [28, 1], [49, -3], [48, 0], [26, 3], [12, 7], [56, 10]],
'w': 5},
[10.5, -3.5, 2.5, -3.5, -2.0, -3.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [41, 12, 50, 46, 3, 104],
'stream': [[41, 0], [12, 1], [50, 3], [46, 1], [3, 4], [30, -2], [32, -3], [41, 10]],
'w': 3},
[12, 4, 4, 4, 4, -1]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [15, 5, 4, 19, 30, 104],
'stream': [[15, 2], [5, -3], [4, 5], [19, -2], [30, -2], [40, -3], [23, 7], [15, 10]],
'w': 6},
[12.0, -3.0, 1.0, -2.0, -4.5, -2.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [5, 41, 39, 54, 1, 104],
'stream': [[5, 0], [41, 5], [39, 2], [54, 1], [1, -2], [52, 7], [13, 5], [5, 10]],
'w': 4},
[12.0, 4.0, 7.0, -4.0, -1.0, -2.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [57, 35, 2, 54, 27, 104],
'stream': [[57, 8], [35, 4], [2, -3], [54, 3], [27, 4], [38, 9], [48, 4], [57, 10]],
'w': 2},
[22, 22, 3, 23, 22, 4]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -7]], 'w': 3},
[0, -7]]]]
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 |
|---|---|---|---|
| stream 0 w=4 d=3 | [-9, 9, 9, -9, 9, -9] | [-1, 9, -3, -9, 9, -6] | Failed |
| stream 1 w=5 d=4 | [11, -5, 5, 5, 8, 5] | [11.5, -2.0, 5.5, 5.0, 8.0, 0.0] | Failed |
| stream 2 w=3 d=5 | [12, 22, 5, 22, -22, 5] | [12, 15, 2, 6, -3, -6] | Failed |
| stream 3 w=6 d=2 | [5, 1, -1, 7, 5, -1] | [4.5, 7.5, 6.5, 9.0, 8.0, -6.0] | Failed |
| stream 4 w=4 d=6 | [16, 16, 4, 5, -4, -16] | [15.0, 3.5, 5.0, 4.5, 0.5, -2.5] | Failed |
| stream 5 w=2 d=3 | [12, -6, -12, -6, 12, 12] | [12, -2, -12, 2, 12, 2] | Failed |
| deletions cancel | [0, -3] | [0, -3] | Passed |
SHA-256 / 2f5ca924bc7df617c9f48571eb3380944cafd301e0709ea90e6de4a4ea2c63a3
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
w = x['w']
d = x['d']
P = 2147483647
A = [1103515245, 1812433253, 1664525017, 2013265921, 1597334677, 1566083941]
B = [12345, 1013904223, 7, 99991, 31337, 424242]
C = [2027373281, 1370461471, 1234567891, 1987654321, 1111111121, 1777777777]
D = [3, 5, 11, 17, 23, 29]
t = [[0] * w for _ in range(d)]
def bucket(r, key):
return (A[r] * key + B[r]) % P % w
def sign(r, key):
return 1 if ((C[r] * key + D[r]) % P) & 1 else -1
for key, cnt in x['stream']:
for r in range(d):
t[r][bucket(r, key)] += sign(r, key) * cnt
out = []
for key in x['queries']:
vals = sorted(sign(r, key) * t[r][bucket(r, key)] for r in range(d))
if d % 2:
out.append(vals[d // 2])
else:
out.append((vals[d // 2 - 1] + vals[d // 2]) / 2)
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['stream 0 w=4 d=3',
{'d': 3,
'queries': [23, 53, 27, 24, 14, 100],
'stream': [[23, -1], [53, 7], [27, 5], [24, -1], [14, 8], [12, 6], [11, 8], [23, 6]],
'w': 4},
[-1, 9, -3, -9, 9, -6]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [26, 55, 10, 15, 19, 100],
'stream': [[26, 5], [55, 1], [10, 6], [15, 5], [19, 8], [8, 9], [59, 0], [26, 6]],
'w': 5},
[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [13, 55, 20, 4, 57, 100],
'stream': [[13, 6], [55, 6], [20, 2], [4, 6], [57, -3], [56, 7], [34, 3], [13, 6]],
'w': 3},
[12, 15, 2, 6, -3, -6]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [52, 50, 14, 47, 13, 100],
'stream': [[52, -2], [50, 8], [14, 7], [47, 7], [13, 1], [6, 3], [2, -1], [52, 6]],
'w': 6},
[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [7, 36, 53, 37, 29, 100],
'stream': [[7, 8], [36, 2], [53, 4], [37, 4], [29, -1], [16, -1], [56, -3], [7, 6]],
'w': 4},
[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [2, 31, 48, 20, 24, 100],
'stream': [[2, 8], [31, 5], [48, 1], [20, 1], [24, -1], [35, 3], [56, 9], [2, 6]],
'w': 2},
[12, -2, -12, 2, 12, 2]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -3]], 'w': 3},
[0, -3]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [47, 24, 9, 42, 45, 101],
'stream': [[47, 5], [24, 3], [9, 3], [42, -1], [45, 0], [39, 9], [50, 1], [47, 7]],
'w': 4},
[15, 4, 3, 2, -3, 0]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [47, 44, 11, 17, 43, 101],
'stream': [[47, 4], [44, 8], [11, 1], [17, 4], [43, -2], [40, 8], [35, 9], [47, 7]],
'w': 5},
[11.0, 5.0, 9.5, 8.0, -2.5, -1.0]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [50, 54, 17, 44, 8, 101],
'stream': [[50, 9], [54, 8], [17, 0], [44, -2], [8, -2], [19, -3], [37, -3], [50, 7]],
'w': 3},
[13, 6, -3, 1, 0, 5]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [53, 40, 34, 19, 50, 101],
'stream': [[53, 0], [40, 6], [34, 5], [19, 9], [50, 3], [41, 4], [16, -3], [53, 7]],
'w': 6},
[0.0, 2.5, 5.0, 5.0, 2.5, -1.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [37, 49, 24, 52, 33, 101],
'stream': [[37, 4], [49, -3], [24, -2], [52, 9], [33, 5], [12, -1], [35, -2], [37, 7]],
'w': 4},
[10.5, -2.0, -3.0, 7.0, 3.5, -5.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [33, 40, 3, 43, 8, 101],
'stream': [[33, 1], [40, 2], [3, 8], [43, 8], [8, 9], [46, 0], [19, -1], [33, 7]],
'w': 2},
[7, 11, 11, 7, -7, -11]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -4]], 'w': 3},
[0, -4]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [26, 43, 31, 44, 30, 102],
'stream': [[26, 7], [43, 0], [31, -2], [44, 9], [30, -1], [10, -1], [41, 3], [26, 8]],
'w': 4},
[12, 1, -2, 7, -1, -12]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [52, 33, 27, 41, 23, 102],
'stream': [[52, 6], [33, -2], [27, 7], [41, 8], [23, 4], [10, -1], [17, 2], [52, 8]],
'w': 5},
[19.0, -11.5, 4.5, 14.0, 4.0, 0.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [30, 59, 54, 34, 46, 102],
'stream': [[30, -3], [59, 2], [54, 7], [34, 3], [46, 4], [10, -2], [43, 6], [30, 8]],
'w': 3},
[12, 6, 12, 1, 3, -6]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [31, 58, 1, 13, 44, 102],
'stream': [[31, 6], [58, 9], [1, -3], [13, 8], [44, 7], [24, 0], [32, -3], [31, 8]],
'w': 6},
[17.5, 10.5, 1.0, 6.5, 15.5, -6.5]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [42, 39, 12, 48, 7, 102],
'stream': [[42, 2], [39, 0], [12, 0], [48, 1], [7, 1], [27, 8], [19, 0], [42, 8]],
'w': 4},
[10.0, 0.5, -0.5, 1.0, 1.0, -1.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [52, 26, 2, 12, 54, 102],
'stream': [[52, -2], [26, 1], [2, 9], [12, 1], [54, 4], [19, 1], [29, 4], [52, 8]],
'w': 2},
[6, -5, 11, 6, 0, -6]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -5]], 'w': 3},
[0, -5]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [17, 20, 22, 7, 59, 103],
'stream': [[17, -2], [20, 3], [22, 1], [7, 6], [59, 2], [53, 4], [21, -1], [17, 9]],
'w': 4},
[4, 0, -2, 3, -4, 3]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [38, 14, 1, 21, 19, 103],
'stream': [[38, -2], [14, 2], [1, -3], [21, 1], [19, 1], [7, 4], [36, 3], [38, 9]],
'w': 5},
[5.0, 0.0, -3.0, 1.5, -6.0, 0.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [47, 31, 6, 26, 18, 103],
'stream': [[47, -3], [31, 0], [6, 6], [26, 6], [18, 2], [38, 9], [10, 9], [47, 9]],
'w': 3},
[10, 0, 8, 8, 2, -9]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [2, 8, 16, 10, 59, 103],
'stream': [[2, 0], [8, 5], [16, -2], [10, 0], [59, -1], [45, -2], [20, -3], [2, 9]],
'w': 6},
[9.0, 6.5, -2.0, 0.0, -2.5, -9.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [42, 41, 28, 10, 22, 103],
'stream': [[42, 5], [41, 1], [28, 9], [10, 6], [22, -3], [56, 5], [34, 5], [42, 9]],
'w': 4},
[12.5, -4.0, 8.5, 6.0, -0.5, -0.5]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [27, 30, 53, 34, 37, 103],
'stream': [[27, 8], [30, 5], [53, 2], [34, 9], [37, -3], [38, -3], [51, 1], [27, 9]],
'w': 2},
[12, 14, 10, 14, 12, 12]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -6]], 'w': 3},
[0, -6]]],
[['stream 0 w=4 d=3',
{'d': 3,
'queries': [49, 2, 6, 18, 34, 104],
'stream': [[49, -1], [2, 7], [6, 0], [18, 7], [34, 7], [8, 5], [1, 3], [49, 10]],
'w': 4},
[6, 0, 4, 7, 7, -3]],
['stream 1 w=5 d=4',
{'d': 4,
'queries': [56, 42, 28, 49, 48, 104],
'stream': [[56, -1], [42, -2], [28, 1], [49, -3], [48, 0], [26, 3], [12, 7], [56, 10]],
'w': 5},
[10.5, -3.5, 2.5, -3.5, -2.0, -3.5]],
['stream 2 w=3 d=5',
{'d': 5,
'queries': [41, 12, 50, 46, 3, 104],
'stream': [[41, 0], [12, 1], [50, 3], [46, 1], [3, 4], [30, -2], [32, -3], [41, 10]],
'w': 3},
[12, 4, 4, 4, 4, -1]],
['stream 3 w=6 d=2',
{'d': 2,
'queries': [15, 5, 4, 19, 30, 104],
'stream': [[15, 2], [5, -3], [4, 5], [19, -2], [30, -2], [40, -3], [23, 7], [15, 10]],
'w': 6},
[12.0, -3.0, 1.0, -2.0, -4.5, -2.0]],
['stream 4 w=4 d=6',
{'d': 6,
'queries': [5, 41, 39, 54, 1, 104],
'stream': [[5, 0], [41, 5], [39, 2], [54, 1], [1, -2], [52, 7], [13, 5], [5, 10]],
'w': 4},
[12.0, 4.0, 7.0, -4.0, -1.0, -2.0]],
['stream 5 w=2 d=3',
{'d': 3,
'queries': [57, 35, 2, 54, 27, 104],
'stream': [[57, 8], [35, 4], [2, -3], [54, 3], [27, 4], [38, 9], [48, 4], [57, 10]],
'w': 2},
[22, 22, 3, 23, 22, 4]],
['deletions cancel',
{'d': 3, 'queries': [7, 8], 'stream': [[7, 4], [7, -4], [8, -7]], 'w': 3},
[0, -7]]]]
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 |
|---|---|---|---|
| stream 0 w=4 d=3 | [-1, 9, -3, -9, 9, -6] | [-1, 9, -3, -9, 9, -6] | Passed |
| stream 1 w=5 d=4 | [11.5, -2.0, 5.5, 5.0, 8.0, 0.0] | [11.5, -2.0, 5.5, 5.0, 8.0, 0.0] | Passed |
| stream 2 w=3 d=5 | [12, 15, 2, 6, -3, -6] | [12, 15, 2, 6, -3, -6] | Passed |
| stream 3 w=6 d=2 | [4.5, 7.5, 6.5, 9.0, 8.0, -6.0] | [4.5, 7.5, 6.5, 9.0, 8.0, -6.0] | Passed |
| stream 4 w=4 d=6 | [15.0, 3.5, 5.0, 4.5, 0.5, -2.5] | [15.0, 3.5, 5.0, 4.5, 0.5, -2.5] | Passed |
| stream 5 w=2 d=3 | [12, -2, -12, 2, 12, 2] | [12, -2, -12, 2, 12, 2] | Passed |
| deletions cancel | [0, -3] | [0, -3] | Passed |
SHA-256 / 19376c6d27909cad00696319805271bba3cf7d684339aaa6748adc80ba32308d
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.136277+00:00.
Case digest / 4d2886842cf2a3388426c8c390cb473a2c54aa7620817b1fdb0ab225e12d62fe