FA-73081 / Probabilistic sketches / Open access

Count sketch frequency estimation: even row count takes the lower middle value · case 01

Sketches with an even number of rows systematically underestimate.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

For even d the lower middle value is returned instead of the mean of the two middle values.

VERIFIED REPAIR

Average the two middle values when d is even.

Unsuccessful approach: Taking the upper middle value biases estimates upward instead.

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))
        if d % 2:
            out.append(vals[d // 2])
        else:
            out.append(vals[d // 2 - 1])
    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, 5, 5, 8, 0]`	`[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]`	Failed
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, 1, -1, 7, 5, -11]`	`[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]`	Failed
stream 4 w=4 d=6	`[14, 1, 4, 4, 0, -4]`	`[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]`	Failed
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 / 4635cd9df5c5fcc0d71e1b26357826fca86f5ed8a884f8f75107edb32f40ac36

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))
        if d % 2:
            out.append(vals[d // 2])
        else:
            out.append(vals[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	`[-1, 9, -3, -9, 9, -6]`	`[-1, 9, -3, -9, 9, -6]`	Passed
stream 1 w=5 d=4	`[12, 1, 6, 5, 8, 0]`	`[11.5, -2.0, 5.5, 5.0, 8.0, 0.0]`	Failed
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	`[5, 14, 14, 11, 11, -1]`	`[4.5, 7.5, 6.5, 9.0, 8.0, -6.0]`	Failed
stream 4 w=4 d=6	`[16, 6, 6, 5, 1, -1]`	`[15.0, 3.5, 5.0, 4.5, 0.5, -2.5]`	Failed
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 / f7ea5396693398304804b1df5166ed0812201c263516a9ae4098c63c25600bc4

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.135878+00:00.

Case digest / 4c0520b23b60c190c124d79baac527be18c964d96de26afc853ac964f36ed49a