FAILURE MAP
← Case archive

FA-73086 / Probabilistic sketches / Open access

Count sketch frequency estimation: update omits the row sign · case 01

Colliding keys accumulate instead of cancelling, and queries multiply unsigned cells by a sign.

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

ROOT CAUSE

Updates add the raw count without multiplying by the key's row sign.

VERIFIED REPAIR

Add sign * count on every update.

Unsuccessful approach: Signing the absolute count turns deletions into insertions.

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)] += 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 fixtureActualExpectedOutcome
stream 0 w=4 d=3[11, -6, 19, -6, 13, -6][-1, 9, -3, -9, 9, -6]Failed
stream 1 w=5 d=4[12.0, 4.0, -6.5, 3.0, 0.0, 0.0][11.5, -2.0, 5.5, 5.0, 8.0, 0.0]Failed
stream 2 w=3 d=5[-12, 6, 15, 6, -12, -5][12, 15, 2, 6, -3, -6]Failed
stream 3 w=6 d=2[-4.5, -14.5, 0.5, -2.0, -8.0, 6.0][4.5, 7.5, 6.5, 9.0, 8.0, -6.0]Failed
stream 4 w=4 d=6[-12.5, -1.5, 5.0, 0.5, 0.0, -1.0][15.0, 3.5, 5.0, 4.5, 0.5, -2.5]Failed
stream 5 w=2 d=3[-14, 18, -18, 18, -2, -14][12, -2, -12, 2, 12, 2]Failed
deletions cancel[0, 3][0, -3]Failed

SHA-256 / ef1ce2ef78a79c6de2953f6a2a0dd2428105d594188f8aedce236b176c5f1377

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) * abs(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 fixtureActualExpectedOutcome
stream 0 w=4 d=3[1, 8, -3, -7, 8, -6][-1, 9, -3, -9, 9, -6]Failed
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, 3, 6, 3, -6][12, 15, 2, 6, -3, -6]Failed
stream 3 w=6 d=2[8.5, 8.5, 7.5, 9.0, 10.0, -5.0][4.5, 7.5, 6.5, 9.0, 8.0, -6.0]Failed
stream 4 w=4 d=6[16.0, 5.0, 5.0, 4.0, 3.0, -3.5][15.0, 3.5, 5.0, 4.5, 0.5, -2.5]Failed
stream 5 w=2 d=3[14, -2, -14, 2, 14, 2][12, -2, -12, 2, 12, 2]Failed
deletions cancel[8, 3][0, -3]Failed

SHA-256 / 1ea8ca2bcf10049d36d75b0ec7ed550356f4b1fc0b36c028e8fd709457c85447

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

Case digest / 2ea27fdc3cf21ca9ccb3ba2e62ee5f2f9555b7102535fed7a7593db614077091