FA-73256 / Probabilistic sketches / Open access
K-minimum-values distinct counting: overlap counted beyond the union sketch · case 01
Shared values larger than the union's k-th value inflate the intersection estimate.
ROOT CAUSE
The overlap counts all common kept values instead of only those inside the union sketch.
THE FAILURE
The overlap counts all common kept values instead of only those inside the union sketch.
Unsuccessful approach: Counting union values kept by A alone ignores B entirely.
Case contract
Input {k, a, b} lists of 32-bit hashes. Each sketch keeps the k smallest distinct hashes. With fewer than k kept values the count is exact (their number); otherwise the estimate is round((k-1) * 2^32 / v_k) with v_k the k-th smallest. The union sketch is the k smallest distinct values of both kept sets. The intersection is exact when the union has fewer than k values, else round(c/k * union estimate) where c counts union-sketch values kept by both inputs. Return [estA, estB, estUnion, estIntersection].
Why this case matters
KMV sketches power approximate COUNT(DISTINCT) with set operations in analytics engines; the unbiased (k-1)/v_k form and the union rule are easy to get subtly wrong.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
def kept(hs):
return sorted(set(hs))[:k]
def est(vals):
if len(vals) < k:
return len(vals)
return round((k - 1) * 2 ** 32 / vals[k - 1])
A = kept(x['a'])
B = kept(x['b'])
U = sorted(set(A) | set(B))[:k]
eu = est(U)
if len(U) < k:
inter = len(set(A) & set(B))
else:
both = len(set(A) & set(B))
inter = round(both / k * eu)
return [est(A), est(B), eu, inter]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['streams 0 k=4',
{'a': [767117601,
1349057482,
512140804,
2709330522,
97797847,
2991703416,
247407200,
502807838,
953930153,
4276337012,
825867426,
927935964,
767117601,
1349057482,
512140804],
'b': [767117601,
1349057482,
512140804,
2709330522,
97797847,
3243866592,
2367279148,
2430077702,
2971523655,
1478379009],
'k': 4},
[25, 10, 25, 12]],
['streams 1 k=5',
{'a': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
844670565,
1574495990,
3092220355,
1623550118,
1677170996,
355484359,
1577212364,
222802868,
3302194479,
1232086826,
4029593972,
846568436,
2280170916,
2039090929,
2369642582],
'b': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
3736327325,
4143402618,
3225214513,
2668680618,
690502660,
4038350892,
2109753841],
'k': 5},
[19, 8, 20, 0]],
['streams 2 k=3',
{'a': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492,
2831125304,
3278849932,
2146240677],
'b': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492],
'k': 3},
[8, 8, 8, 8]],
['streams 3 k=6',
{'a': [1347661301,
1126717335,
1593064253,
3578257729,
3263214743,
1485141222,
507376609,
870194170,
405495016,
463928501,
3212162911,
200606854,
3827729694,
3442164173,
3023093882,
3815698597,
1832272475,
945613159,
136487868,
1731202674,
3903788721,
2182062801,
1489904681,
708728146,
1980483838,
1269587876,
3424059671,
3167970027,
3314237818,
161588255,
1347661301,
1126717335,
1593064253],
'b': [1347661301,
1126717335,
1593064253,
3578257729,
1184217959,
795322907,
2681969582,
1479728863,
915549410,
1616093956,
1998008578,
566339276],
'k': 6},
[42, 16, 42, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
2958152150,
1105148405,
1551545311,
2382410247,
299374495,
3902367104,
3814609907,
616469427,
2903262975,
2673828359],
'b': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
1904501607,
2415525956,
972943297,
1101134287,
4209348669],
'k': 4},
[12, 12, 13, 6]],
['streams 1 k=5',
{'a': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
3882412494,
3638249284,
629708383,
2652904385,
619827854,
2252659737,
4038367328,
751384629,
2736132274,
2052511795,
1546656212,
2490980400,
1192536461,
3397803296,
3575214874],
'b': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
801257707,
231860101,
1552367569,
2200650299,
1300574527,
1169595163,
1486586779],
'k': 5},
[14, 14, 23, 5]],
['streams 2 k=3',
{'a': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795,
3366336454,
3360405550,
3252767639],
'b': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795],
'k': 3},
[4, 4, 4, 4]],
['streams 3 k=6',
{'a': [1412588383,
1682740534,
1107531143,
3554458900,
2859580621,
3296482680,
2191809106,
4155174719,
3651321607,
3668767012,
3871583709,
53568284,
232037959,
2442976016,
217741541,
3800768541,
2101516655,
2409083912,
918078055,
2969028849,
3001715579,
3922319082,
2100936555,
2284049623,
3774876442,
3238172673,
3672802287,
3806827876,
2442511505,
3389659053,
1412588383,
1682740534,
1107531143],
'b': [1412588383,
1682740534,
1107531143,
3554458900,
321792195,
4055119656,
4005216604,
4067339772,
2438348428,
2893845634,
4168021051,
1191737207],
'k': 6},
[15, 9, 19, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
874550077,
874052348,
2099297276,
2917681254,
3461079448,
4523874,
1892412104,
1348947199,
2220012561,
4274378431],
'b': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
320314762,
2913424927,
3760403017,
3874375803,
3498294633],
'k': 4},
[15, 8, 15, 4]],
['streams 1 k=5',
{'a': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
429269052,
4120988501,
2192756914,
2080257154,
215643658,
2236181558,
3506517446,
3204080191,
2539102762,
1231819029,
129435166,
1969895105,
1451722624,
4208772152,
2008054505],
'b': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
3624728915,
4097927174,
3560188535,
2101457494,
1008357362,
2961406180,
2250944138],
'k': 5},
[45, 13, 45, 27]],
['streams 2 k=3',
{'a': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124,
163959442,
4243274568,
1097577740],
'b': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124],
'k': 3},
[28, 28, 28, 28]],
['streams 3 k=6',
{'a': [3736875704,
2512119594,
3432728552,
1249721439,
4076278131,
1681936286,
3644273863,
1144985545,
1058589555,
2372866836,
2747157307,
319015226,
1616345963,
3215957022,
2575778964,
2002333856,
105152923,
971771153,
3904739092,
139512839,
3596088601,
3125993293,
3698817286,
571115313,
2651377839,
404892510,
335085347,
3997319691,
423428202,
1253418186,
3736875704,
2512119594,
3432728552],
'b': [3736875704,
2512119594,
3432728552,
1249721439,
2190917676,
1217641816,
2195352441,
1962797028,
1369215451,
146219861,
2422264426,
2740291298],
'k': 6},
[51, 10, 53, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
469293850,
3311372855,
3291632216,
3532104316,
792576761,
2383663819,
3796612359,
534629630,
3752143492,
3784451643],
'b': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
778329530,
4126190270,
369138172,
3244871941,
426427744],
'k': 4},
[5, 17, 24, 6]],
['streams 1 k=5',
{'a': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
2365171429,
473117839,
1494688212,
3130081894,
3456600902,
1870835644,
1831585095,
856053019,
2401707901,
8291469,
994865049,
2075147938,
2281118336,
470394482,
2564274781],
'b': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
3616671026,
3377000285,
291138770,
4144176995,
410153163,
1894447883,
2251698],
'k': 5},
[36, 42, 59, 24]],
['streams 2 k=3',
{'a': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100,
3123627193,
2732919500,
1916452664],
'b': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100],
'k': 3},
[25, 25, 25, 25]],
['streams 3 k=6',
{'a': [920449838,
3707669583,
2705746824,
603387996,
145050205,
1943098641,
2902033596,
942056830,
1094682071,
482655062,
1597161973,
2776457123,
540173509,
49617459,
3062849472,
721066780,
1881851915,
2771669550,
271560229,
4250659366,
849113494,
2890310823,
2849978717,
2813753673,
2723489037,
3843541794,
2539258177,
294140292,
131741950,
1174692757,
920449838,
3707669583,
2705746824],
'b': [920449838,
3707669583,
2705746824,
603387996,
396707761,
853541794,
990402306,
2774188573,
1932619200,
40971593,
4209408016,
3008903819],
'k': 6},
[44, 22, 73, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
3402435104,
2615317700,
2901867586,
2191387195,
3244643901,
143617512,
4128185702,
3695416152,
3485519680,
1295479236],
'b': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
2172377362,
122431251,
2879905546,
3080363355,
742472857],
'k': 4},
[6, 6, 10, 2]],
['streams 1 k=5',
{'a': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3856414966,
182199786,
3302563887,
3489282613,
3728782849,
2555406465,
3392268813,
468049757,
2334691707,
3652253765,
2830979039,
2618409554,
629677788,
1134145340,
1003578828],
'b': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3383921903,
1576598490,
1966729080,
3816342364,
951010101,
559264201,
3070372495],
'k': 5},
[17, 17, 27, 11]],
['streams 2 k=3',
{'a': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371,
618180559,
2081251765,
530858903],
'b': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371],
'k': 3},
[14, 14, 14, 14]],
['streams 3 k=6',
{'a': [1308497545,
1688068524,
2659577736,
1794751184,
3886248964,
2353903802,
3929595655,
3522020961,
4226953245,
1619288587,
3373914572,
808857433,
2095738713,
3699811607,
2323854089,
4254321459,
2563706603,
1910759716,
2164426481,
690823666,
2412713602,
1704719407,
2407797195,
541403854,
3575208143,
381803083,
3474890246,
3033023633,
2039329698,
3301104757,
1308497545,
1688068524,
2659577736],
'b': [1308497545,
1688068524,
2659577736,
1794751184,
923787522,
3928497192,
1582544665,
3091940628,
1369092784,
2483888591,
2347320516,
1678251482],
'k': 6},
[13, 13, 16, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]]]
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 |
|---|---|---|---|
| streams 0 k=4 | [25, 10, 25, 12] | [25, 10, 25, 12] | Passed |
| streams 1 k=5 | [19, 8, 20, 4] | [19, 8, 20, 0] | Failed |
| streams 2 k=3 | [8, 8, 8, 8] | [8, 8, 8, 8] | Passed |
| streams 3 k=6 | [42, 16, 42, 0] | [42, 16, 42, 0] | Passed |
| small exact sets | [3, 2, 4, 1] | [3, 2, 4, 1] | Passed |
| exactly k distinct | [29, 2, 43, 14] | [29, 2, 43, 14] | Passed |
| shared value beyond union sketch | [14, 14, 43, 14] | [14, 14, 43, 0] | Failed |
| duplicated small hashes | [6, 954437177, 954437177, 318145726] | [6, 954437177, 954437177, 318145726] | Passed |
SHA-256 / 73c810172c3f29338795b2743af89a524febb3b41520b02198ae4dfbd9d1a6ed
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
k = x['k']
def kept(hs):
return sorted(set(hs))[:k]
def est(vals):
if len(vals) < k:
return len(vals)
return round((k - 1) * 2 ** 32 / vals[k - 1])
A = kept(x['a'])
B = kept(x['b'])
U = sorted(set(A) | set(B))[:k]
eu = est(U)
if len(U) < k:
inter = len(set(A) & set(B))
else:
both = sum(1 for v in U if v in A)
inter = round(both / k * eu)
return [est(A), est(B), eu, inter]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['streams 0 k=4',
{'a': [767117601,
1349057482,
512140804,
2709330522,
97797847,
2991703416,
247407200,
502807838,
953930153,
4276337012,
825867426,
927935964,
767117601,
1349057482,
512140804],
'b': [767117601,
1349057482,
512140804,
2709330522,
97797847,
3243866592,
2367279148,
2430077702,
2971523655,
1478379009],
'k': 4},
[25, 10, 25, 12]],
['streams 1 k=5',
{'a': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
844670565,
1574495990,
3092220355,
1623550118,
1677170996,
355484359,
1577212364,
222802868,
3302194479,
1232086826,
4029593972,
846568436,
2280170916,
2039090929,
2369642582],
'b': [2280170916,
2039090929,
2369642582,
1720999519,
2642080423,
1889774005,
2089713092,
881963964,
3736327325,
4143402618,
3225214513,
2668680618,
690502660,
4038350892,
2109753841],
'k': 5},
[19, 8, 20, 0]],
['streams 2 k=3',
{'a': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492,
2831125304,
3278849932,
2146240677],
'b': [2831125304,
3278849932,
2146240677,
1030875024,
3846626178,
118622987,
1526835452,
1968349859,
112867492],
'k': 3},
[8, 8, 8, 8]],
['streams 3 k=6',
{'a': [1347661301,
1126717335,
1593064253,
3578257729,
3263214743,
1485141222,
507376609,
870194170,
405495016,
463928501,
3212162911,
200606854,
3827729694,
3442164173,
3023093882,
3815698597,
1832272475,
945613159,
136487868,
1731202674,
3903788721,
2182062801,
1489904681,
708728146,
1980483838,
1269587876,
3424059671,
3167970027,
3314237818,
161588255,
1347661301,
1126717335,
1593064253],
'b': [1347661301,
1126717335,
1593064253,
3578257729,
1184217959,
795322907,
2681969582,
1479728863,
915549410,
1616093956,
1998008578,
566339276],
'k': 6},
[42, 16, 42, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 41], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000001, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000001, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000001, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
2958152150,
1105148405,
1551545311,
2382410247,
299374495,
3902367104,
3814609907,
616469427,
2903262975,
2673828359],
'b': [616469427,
2903262975,
2673828359,
389501480,
3344127933,
1904501607,
2415525956,
972943297,
1101134287,
4209348669],
'k': 4},
[12, 12, 13, 6]],
['streams 1 k=5',
{'a': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
3882412494,
3638249284,
629708383,
2652904385,
619827854,
2252659737,
4038367328,
751384629,
2736132274,
2052511795,
1546656212,
2490980400,
1192536461,
3397803296,
3575214874],
'b': [1192536461,
3397803296,
3575214874,
1217859995,
3883808108,
1269760818,
296997750,
1572046585,
801257707,
231860101,
1552367569,
2200650299,
1300574527,
1169595163,
1486586779],
'k': 5},
[14, 14, 23, 5]],
['streams 2 k=3',
{'a': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795,
3366336454,
3360405550,
3252767639],
'b': [3366336454,
3360405550,
3252767639,
2239802314,
1962451971,
4237034881,
2990495608,
2652720588,
2235033795],
'k': 3},
[4, 4, 4, 4]],
['streams 3 k=6',
{'a': [1412588383,
1682740534,
1107531143,
3554458900,
2859580621,
3296482680,
2191809106,
4155174719,
3651321607,
3668767012,
3871583709,
53568284,
232037959,
2442976016,
217741541,
3800768541,
2101516655,
2409083912,
918078055,
2969028849,
3001715579,
3922319082,
2100936555,
2284049623,
3774876442,
3238172673,
3672802287,
3806827876,
2442511505,
3389659053,
1412588383,
1682740534,
1107531143],
'b': [1412588383,
1682740534,
1107531143,
3554458900,
321792195,
4055119656,
4005216604,
4067339772,
2438348428,
2893845634,
4168021051,
1191737207],
'k': 6},
[15, 9, 19, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 42], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000002, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000002, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000002, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
874550077,
874052348,
2099297276,
2917681254,
3461079448,
4523874,
1892412104,
1348947199,
2220012561,
4274378431],
'b': [1348947199,
2220012561,
4274378431,
1679674411,
803241050,
320314762,
2913424927,
3760403017,
3874375803,
3498294633],
'k': 4},
[15, 8, 15, 4]],
['streams 1 k=5',
{'a': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
429269052,
4120988501,
2192756914,
2080257154,
215643658,
2236181558,
3506517446,
3204080191,
2539102762,
1231819029,
129435166,
1969895105,
1451722624,
4208772152,
2008054505],
'b': [1451722624,
4208772152,
2008054505,
153986199,
31834739,
1286658403,
379682339,
3141003873,
3624728915,
4097927174,
3560188535,
2101457494,
1008357362,
2961406180,
2250944138],
'k': 5},
[45, 13, 45, 27]],
['streams 2 k=3',
{'a': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124,
163959442,
4243274568,
1097577740],
'b': [163959442,
4243274568,
1097577740,
311555763,
710797651,
965433560,
3806058722,
449325668,
242872124],
'k': 3},
[28, 28, 28, 28]],
['streams 3 k=6',
{'a': [3736875704,
2512119594,
3432728552,
1249721439,
4076278131,
1681936286,
3644273863,
1144985545,
1058589555,
2372866836,
2747157307,
319015226,
1616345963,
3215957022,
2575778964,
2002333856,
105152923,
971771153,
3904739092,
139512839,
3596088601,
3125993293,
3698817286,
571115313,
2651377839,
404892510,
335085347,
3997319691,
423428202,
1253418186,
3736875704,
2512119594,
3432728552],
'b': [3736875704,
2512119594,
3432728552,
1249721439,
2190917676,
1217641816,
2195352441,
1962797028,
1369215451,
146219861,
2422264426,
2740291298],
'k': 6},
[51, 10, 53, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 43], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000003, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000003, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000003, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
469293850,
3311372855,
3291632216,
3532104316,
792576761,
2383663819,
3796612359,
534629630,
3752143492,
3784451643],
'b': [534629630,
3752143492,
3784451643,
3707448500,
3478884196,
778329530,
4126190270,
369138172,
3244871941,
426427744],
'k': 4},
[5, 17, 24, 6]],
['streams 1 k=5',
{'a': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
2365171429,
473117839,
1494688212,
3130081894,
3456600902,
1870835644,
1831585095,
856053019,
2401707901,
8291469,
994865049,
2075147938,
2281118336,
470394482,
2564274781],
'b': [2281118336,
470394482,
2564274781,
1456576635,
76225771,
1929399051,
3087256315,
11795723,
3616671026,
3377000285,
291138770,
4144176995,
410153163,
1894447883,
2251698],
'k': 5},
[36, 42, 59, 24]],
['streams 2 k=3',
{'a': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100,
3123627193,
2732919500,
1916452664],
'b': [3123627193,
2732919500,
1916452664,
2995221416,
344825209,
1320214633,
116279824,
3826515764,
83053100],
'k': 3},
[25, 25, 25, 25]],
['streams 3 k=6',
{'a': [920449838,
3707669583,
2705746824,
603387996,
145050205,
1943098641,
2902033596,
942056830,
1094682071,
482655062,
1597161973,
2776457123,
540173509,
49617459,
3062849472,
721066780,
1881851915,
2771669550,
271560229,
4250659366,
849113494,
2890310823,
2849978717,
2813753673,
2723489037,
3843541794,
2539258177,
294140292,
131741950,
1174692757,
920449838,
3707669583,
2705746824],
'b': [920449838,
3707669583,
2705746824,
603387996,
396707761,
853541794,
990402306,
2774188573,
1932619200,
40971593,
4209408016,
3008903819],
'k': 6},
[44, 22, 73, 0]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 44], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000004, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000004, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000004, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]],
[['streams 0 k=4',
{'a': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
3402435104,
2615317700,
2901867586,
2191387195,
3244643901,
143617512,
4128185702,
3695416152,
3485519680,
1295479236],
'b': [3695416152,
3485519680,
1295479236,
2096590373,
3787333106,
2172377362,
122431251,
2879905546,
3080363355,
742472857],
'k': 4},
[6, 6, 10, 2]],
['streams 1 k=5',
{'a': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3856414966,
182199786,
3302563887,
3489282613,
3728782849,
2555406465,
3392268813,
468049757,
2334691707,
3652253765,
2830979039,
2618409554,
629677788,
1134145340,
1003578828],
'b': [629677788,
1134145340,
1003578828,
4058355717,
2251438880,
2144550018,
3171525108,
367867543,
3383921903,
1576598490,
1966729080,
3816342364,
951010101,
559264201,
3070372495],
'k': 5},
[17, 17, 27, 11]],
['streams 2 k=3',
{'a': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371,
618180559,
2081251765,
530858903],
'b': [618180559,
2081251765,
530858903,
86152431,
2519876564,
1646187280,
3524098075,
1367524039,
2583752371],
'k': 3},
[14, 14, 14, 14]],
['streams 3 k=6',
{'a': [1308497545,
1688068524,
2659577736,
1794751184,
3886248964,
2353903802,
3929595655,
3522020961,
4226953245,
1619288587,
3373914572,
808857433,
2095738713,
3699811607,
2323854089,
4254321459,
2563706603,
1910759716,
2164426481,
690823666,
2412713602,
1704719407,
2407797195,
541403854,
3575208143,
381803083,
3474890246,
3033023633,
2039329698,
3301104757,
1308497545,
1688068524,
2659577736],
'b': [1308497545,
1688068524,
2659577736,
1794751184,
923787522,
3928497192,
1582544665,
3091940628,
1369092784,
2483888591,
2347320516,
1678251482],
'k': 6},
[13, 13, 16, 3]],
['small exact sets', {'a': [10, 20, 30, 20], 'b': [20, 45], 'k': 5}, [3, 2, 4, 1]],
['exactly k distinct',
{'a': [100000000, 200000005, 300000000], 'b': [100000000, 5], 'k': 3},
[29, 2, 43, 14]],
['shared value beyond union sketch',
{'a': [100000000, 200000005, 600000000], 'b': [150000000, 250000000, 600000000], 'k': 3},
[14, 14, 43, 0]],
['duplicated small hashes',
{'a': [7, 7, 7, 900000000, 1500000005, 2000000000], 'b': [7, 8, 9, 10], 'k': 3},
[6, 954437177, 954437177, 318145726]]]]
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 |
|---|---|---|---|
| streams 0 k=4 | [25, 10, 25, 25] | [25, 10, 25, 12] | Failed |
| streams 1 k=5 | [19, 8, 20, 16] | [19, 8, 20, 0] | Failed |
| streams 2 k=3 | [8, 8, 8, 8] | [8, 8, 8, 8] | Passed |
| streams 3 k=6 | [42, 16, 42, 42] | [42, 16, 42, 0] | Failed |
| small exact sets | [3, 2, 4, 1] | [3, 2, 4, 1] | Passed |
| exactly k distinct | [29, 2, 43, 29] | [29, 2, 43, 14] | Failed |
| shared value beyond union sketch | [14, 14, 43, 29] | [14, 14, 43, 0] | Failed |
| duplicated small hashes | [6, 954437177, 954437177, 318145726] | [6, 954437177, 954437177, 318145726] | Passed |
SHA-256 / 70d1f6d1f0e0426e88bb8604f8bc91c731d9946b2a986de0b5a94b17155d9bb7
HELD IN THE MEMBER ARCHIVE
The verified repair and its recorded checks are member-only.
This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.
Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.
Member access is invitation-based. Sign in with your invited account to inspect the repair.
Sign in to the archive ↗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:45.922670+00:00.
Case digest / 6e9dae4a537d07f4e14a7195142a38212258a7d27e423f11983833984587cdc0