FA-73232 / Probabilistic sketches / Member archive

MinHash LSH banding: pairs reported in both orders · case 02

The verifier compares every candidate twice, once per ordering.

Member previewVariant 2 · 3 implementations · 8 checks per implementation

Case contract

Input {b, r, sigs} with sigs a list of [id, signature]. Every signature must have exactly b*r components, otherwise "invalid". Band i covers components i*r .. i*r+r-1 and hashes to the key (i, band tuple). Ids sharing any band key form a candidate pair [smaller, larger], reported once, sorted. Also return the similarity threshold (1/b)^(1/r) rounded to 3 decimals.

Why this case matters

Locality-sensitive hashing prunes all-pairs similarity search; banding mistakes either flood the verifier with false candidates or silently miss near-duplicates.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
bands 0 b=3 r=2	`[[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]], 0.577]`	`[[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], 0.577]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.