FA-73246 / Probabilistic sketches / Open access
K-minimum-values distinct counting: full sketch reported as an exact count · case 01
A sketch holding exactly k values reports k, although the true distinct count may be far larger.
ROOT CAUSE
The exact-count branch uses <= k, so a full sketch never reaches the estimator.
THE FAILURE
The exact-count branch uses <= k, so a full sketch never reaches the estimator.
Unsuccessful approach: Returning k in the exact regime reports capacity instead of the true count.
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 = sum(1 for v in U if v in A and v in 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 | [4, 4, 4, 2] | [25, 10, 25, 12] | Failed |
| streams 1 k=5 | [5, 5, 5, 0] | [19, 8, 20, 0] | Failed |
| streams 2 k=3 | [3, 3, 3, 3] | [8, 8, 8, 8] | Failed |
| streams 3 k=6 | [6, 6, 6, 0] | [42, 16, 42, 0] | Failed |
| small exact sets | [3, 2, 4, 1] | [3, 2, 4, 1] | Passed |
| exactly k distinct | [3, 2, 3, 1] | [29, 2, 43, 14] | Failed |
| shared value beyond union sketch | [3, 3, 3, 0] | [14, 14, 43, 0] | Failed |
| duplicated small hashes | [3, 3, 3, 1] | [6, 954437177, 954437177, 318145726] | Failed |
SHA-256 / bb573d99adbf0a8b1a1caf90f6284343399beaea22c62f3c3f84c8f93d02b633
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 k
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 and v in 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, 0] | [19, 8, 20, 0] | Passed |
| 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 | [5, 5, 5, 1] | [3, 2, 4, 1] | Failed |
| exactly k distinct | [29, 3, 43, 14] | [29, 2, 43, 14] | Failed |
| shared value beyond union sketch | [14, 14, 43, 0] | [14, 14, 43, 0] | Passed |
| duplicated small hashes | [6, 954437177, 954437177, 318145726] | [6, 954437177, 954437177, 318145726] | Passed |
SHA-256 / 4519f8677c1dc3f4e5b99c91fa3bb6ede414ba54d12657fc89bf02e58402021f
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 / fc10eafdbd174e86c09258a4f7fd1b8d5ff21579e2b54bae1334d0cea1e799e7